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
Line 2: N space-separated integers
Output
One integer, the next number in the sequence OR the string "Invalid "
Constraints
3 ≤ N ≤ 15
-1000 ≤ each number in sequence ≤ 1000
Output must either be "Invalid " or an integer between -1000 and 1000
-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