## Fibonaccilike

Statement

## Goal

Adam is trying out various sequences similar to Fibonacci sequences. He starts with two numbers, and keeps iteratively getting the next number in the sequence by adding the two previous numbers.After a point, Adam always gets stuck, and he looks to you for help in finding the next number in the sequence. Given the sequence of numbers generated by Adam, find the next Fibonacci-like number in the sequence.

Unfortunately, Adam sometimes makes a mistake while creating this sequence. In such situations, you need to tell Adam that his sequence is

**invalid**and he needs to fix it before continuing.

**Note:**The first two numbers in the sequence define the sequence, and will never be considered wrong.

If the sequence of numbers is a valid Fibonacci-like sequence, print the next number in the sequence. If the sequence is invalid, print the string "

Input

**Line 1:**An integer

`N`for the number of values that follow

**Line 2:**

`N`space-separated integers

Output

One integer, the next number in the sequence Invalid "

**OR**the string "Constraints

3 ≤

-1000 ≤ each number in sequence ≤ 1000

Output must either be "Invalid " or an integer between -1000 and 1000

`N`≤ 15-1000 ≤ each number in sequence ≤ 1000

Output must either be "

Example

Input

6 5 8 13 21 34 55

Output

89

Game modes

Fastest, Shortest, Reverse

Test cases

Test 1 Test

Input

6
5 8 13 21 34 55

Output

89

Validator 1 Validator

Input

7
1 1 2 3 5 8 13

Output

21

Test 2 Test

Input

5
1 0 1 1 2

Output

3

Validator 2 Validator

Input

3
1 0 1

Output

1

Test 3 Test

Input

6
1 1 2 3 6 9

Output

Invalid

Validator 3 Validator

Input

6
2 3 6 9 22 49

Output

Invalid

Test 5 Test

Input

4
1 -1 0 -1

Output

-1

Validator 5 Validator

Input

5
3 -3 0 -3 -3

Output

-6

Test 6 Test

Input

4
5 5 10 15

Output

25

Validator 6 Validator

Input

5
4 8 12 20 32

Output

52

Test 7 Test

Input

3
6 12 18

Output

30

Validator 7 Validator

Input

6
2 3 6 9 15 24

Output

Invalid

Solution language

Solution

Stub generator input

Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!

JOIN US ON DISCORD Online Participants