Contar Tanques

Durante a Segunda Guerra Mundial, um dos problemas dos Aliados era estimar a capacidade de produção de tanques da Alemanha Nazi. Os serviços de espionagem fizeram uma estimativa, que se mostrou ser bastante exagerada, e foi também pedido a um grupo de matemáticos que resolvessem o problema.

Para este fim, foram recolhidos os vários números de série dos tanques inimigos capturados. Os números de série das caixas de velocidades foram particularmente úteis porque eram sequenciais e recomeçavam (em 1) a cada mês. Ou seja, as caixas de velocidades indicavam o mês em que foram produzidas e um número sequencial. Isto era útil aos Nazis para controlo de qualidade mas expunha informação aos Aliados. No entanto, os Aliados capturavam apenas alguns dos tanques produzidos. Como saber qual a produção num dado mês?

Suponhamos que os números de série dos tanques capturados num mesmo mês eram os números $s_1<s_2<\cdots <s_k$ (portanto, os valores $s_i$ estão por ordem crescente). Uma primeira estimativa seria tomar $s_k$, o maior número de série de um tanque capturado, como o número de tanques produzidos. Mas, provavelmente, teriam sido produzidos mais, porque a probabilidade de ter sido capturado o último da série é baixa. Uma melhor estimativa é somar a este valor a média dos tamanhos dos intervalos entre números de série consecutivos. Por exemplo, a quantidade de números entre 6 e 9 (que são 7 e 8) é $2=9-6-1$. Se forem dois números consecutivos, como 4 e 5, o tamanho do intervalo é $0=5-4-1$. Para o primeiro número da série, consideramos que o anterior é 0. Por exemplo, se o primeiro número for 2, o tamanho do intervalo inicial é $1=2-0-1$.

Os matemáticos mostraram que a melhor estimativa da produção de tanques, dada uma sequência por ordem crescente de números de série $s_1,\dots ,s_k$ (com $k\ge 1$), e considerando $s_0=0$, é dada pela seguinte expressão (onde $\sum$ denota um somatório):

No final da guerra, quando puderam ser analisados os registos da fábrica que produzia as caixas de velocidades dos tanques, constatou-se que o erro obtido por este método era bastante reduzido, geralmente inferior a 20%, contrastando com o das estimativas dos serviços de espionagem, que era da ordem dos 500%.

Este método ainda é usado hoje em dia em espionagem industrial. Se uma empresa usa números sequenciais nos seus produtos (carros, computadores ou telemóveis, por exemplo), a concorrência pode facilmente estimar quantos são produzidos recorrendo a este método.

Tarefa

Input

Restrições

	$0<k<1000$	Quantidade de números de série
	$0<s_i<1000$	Um número de série (para $i=1,\dots ,k$)

Output

Exemplo 1

Input

1
12

Output

23

Exemplo 2

Input

3
4
9
14

Output

17

Exemplo 3

Input

3
4
9
15

Output

19

Exemplo 4

Input

3
4
9
16

Output

20