A. Pincel largo

Time limit: 3000 msMemory limit: 256 MB

Uma faixa tem $n$ casas, inicialmente sem tinta. Cada pincelada escolhe um trecho de pelo menos duas casas consecutivas e acrescenta uma camada de tinta a cada casa desse trecho. Não é possível retirar tinta.

A casa $i$ deve terminar com exatamente $a_i$ camadas. Determine a menor quantidade de pinceladas necessária, ou informe que isso é impossível.

Input

A primeira linha contém $n$ ( $1 \le n \le 200\,000$ ). A segunda contém $a_1,\ldots,a_n$ ().

Output

Imprima o mínimo de pinceladas, ou -1 se não for possível. Se todas as casas já tiverem a quantidade desejada, a resposta é zero.

Samples

Sample 1

Input

5
1 2 1 2 1

Output

Pinte os trechos de casas [1,2], [2,4] e [4,5].

Sample 2

Input

3
1 3 1

Output

-1

Toda pincelada que passa pela casa central também passa por uma das outras casas. As duas casas externas só podem receber duas camadas ao todo.