#2000 삼보나치 수열

23  1 s   128 MB  

Description

삼보나치 수열은 수열의 맨 앞의 세개의 숫자 A[0], A[1], A[2]를 정의하고 다음의 점화식을 통해 계산을 한다:

정확히 하나의 숫자가 정해지지 않은 길이가 N인 삼보나치 수열( A[0] 부터 A[N-1] )이 주어졌을 때, 해당 숫자를 알맞게 정해서 삼보나치 수열을 만드는 프로그램을 작성하라.

주의: 단, 삼보나치 수열을 이루는 숫자는 반드시 양의 정수여야 한다.

Input

입력의 첫 줄에는 입력되는 삼보나치 수열의 길이 N이 입력된다. N은 4이상 20이하의 정수다.

그 다음 줄에는 A[0], A[1], ..., A[N-1]이 순서대로 입력되며, 값이 정해진 숫자의 경우에는 1이상 1,000,000이하의 숫자로 입력된다. 값이 정해지지 않은 숫자의 경우에는 -1로 표기되며, -1은 정확히 한번만 입력된다.

Output

삼보나치 수열이 되도록 정해지지 않은 숫자를 바꿨을 때 해당 숫자를 출력한다. 만약 삼보나치 수열을 만들 수 없는 경우 -1을 출력한다.

Sample Input

Sample Output

4
1 2 3 -1
6

Sample Input 2

5
1 1 -1 2 3

Sample Output 2

-1