Find the Missing Bajtek Element

You are given a sequence of numbers which is supposed to follow the recurrence relation of a Fibonacci-like sequence given by the formula: $$a_i = a_{i-1} + a_{i-2}$$ for all \( i \ge 3 \). However, one element is missing in the sequence. Your task is to determine the missing element.

The sequence provided is the original sequence after the removal of exactly one element. If a discrepancy occurs in the middle of the sequence, it indicates the gap due to the removed element and you should compute it using the recurrence relation. If no such discrepancy is found, then the missing element is the next element in the sequence.

For example, if the input sequence is 1 1 2 3 5 8 13 21 34 (with an expected 10th element), the correct missing element is 55 because 34 + 21 = 55.

inputFormat

The input is read from stdin and consists of two lines:

• The first line contains an integer n which is the number of elements in the sequence after one element has been removed.
• The second line contains n space-separated integers representing the remaining elements of the sequence.

outputFormat

Output to stdout a single integer representing the missing element in the sequence.

9
1 1 2 3 5 8 13 21 34

55