K. Picolés e triângulos
time limit per test
0.25 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Magali adora picolés. Quando ela termina de comer, ela dá o palito para Cebolinha, que tenta montar um triângulo com os palitos que já lhe foram dados. Assim que ele consegue montar, cebolinha sai satisfeito.

Você deve dizer quantos palitos Cebolinha tinha no momento em que ele concluiu seu triângulo ou dizer se isso nunca acontecer.

Input

A primeira linha contém um inteiro N, 1 ≤ N ≤ 5·107, o número de palitos comidos por Magali. Seguem N linhas, a i-ésima com um inteiro pi, 1 ≤ pi ≤ 1018, o tamanho dos palitos, em cm, na ordem que Magali os come (e dá para Cebolinha).

Note que alguns palitos podem ser MUITO grandes. Se estiver usando C/C++/Java use inteiros de 64-bits (long long para C++). Para Python não tem problema.

Output

Um inteiro K que diz quantos palitos o Cebolinha tinha quando ele finalmente montou seu triângulo ou -1 caso ele nunca consiga.

Examples
Input
6
1
1
2
3
1
2
Output
5
Input
3
1
2
3
Output
-1
Input
2
5
5
Output
-1
Input
3
100000000000000000
100000000000000000
100000000000000001
Output
3
Note

Por exemplo, se Magali comeu, nessa ordem, palitos de tamanho 1,1,2,3,1,1. Apenas após o 5º palito ele consegue formar um triângulo, usando os palitos {1,1,1}. Note que com os palitos de tamanho {1,1,2} é possível formar um "triângulo degenerado" (uma reta), mas isso não conta!