Next Term in a Sequence

Interview

Time limit2sMemory limit128 MB

Summary

Given a sequence that is either arithmetic or geometric, determine which type it is and output its next term.

Level: Easy2 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

An arithmetic sequence with an integer common difference can be described by two integers P and Q. P is the first term, and Q is the value added to the previous term to get the next one. For example, if P=1 and Q=2, the sequence is 1, 3, 5, 7, ... .

A geometric sequence with an integer common ratio can also be described by two integers P and Q. P is the first term, and Q is the value multiplied by the previous term to get the next one. For example, if P=3 and Q=2, the sequence is 3, 6, 12, ... .

Teddy decides every day whether a given sequence is arithmetic or geometric, then finds its next term.

The given sequence follows one of the two rules above. Write a program that finds the rule and prints the next number.

Input

The first line contains the length N of the sequence. Each of the next N lines contains one term of the sequence in order.

The given sequence is either arithmetic or geometric. N is always between 3 and 50 inclusive, and every input number is a natural number no greater than 10^6.

Output

Print the next term of the sequence on the first line. This number is a natural number no greater than 2,000,000,000.

Examples5

Example 1
Input
```
4
364
843
1322
1801
```
Expected output
```
2280
```

Example 2

Input

Expected output

Example 3
Input
```
5
13
117
1053
9477
85293
```
Expected output
```
767637
```
Example 4
Input
```
4
22
220
2200
22000
```
Expected output
```
220000
```
Example 5
Input
```
3
250000
500000
1000000
```
Expected output
```
2000000
```