It was late Saturday morning at the end of October. The amusement park was going to be open that afternoon for the first time after months of prolonged reconstruction.

Josse and Murry were sitting in the basement of the office building at the park gate. They have just finished debugging their advanced AI system management of all fantastic attractions in the park. "Work is done," said Josse. "Now for some amusement. Can you think of any algorithmic problem?"

"Yes, of course," replied Murry and grinned at his friend from his heavily cluttered desk. "Consider, for example, finite sequences of numbers. For me, the most interesting sequences are those that end with a long arithmetic sequence. In other words, I like arithmetic sequences that span from some index to the very last member. As there may be many such subsequences, in order to truly appreciate how interesting some sequence is, it is necessary to determine which one is the longest. Here is your initial sequence. You have to find the start of the longest continuous arithmetic subsequence spanning to its end."

"OK," said Josse when he marked the correct place in the sequence. "That was easy. What next?" "What next?" Repeated Murry and hesitated for a moment. Then he raised himself determinedly from the chair. "Let's go out to the park and find some tougher problems there!"

Input Specification

There are more test cases. Each case consists of two lines. The first line contains one integer ~N~ ~(1 \le N \le 1000)~ specifying the length of the sequence. The second line contains a sequence of ~N~ integers ~X_i~ ~(0 \le X_i \le 10^9)~, separated by spaces.

Output Specification

For each test case, print a single line with the index of the first member of the longest continuous arithmetic subsequence that spans to the end of the given sequence. The index of the first element in the sequence is always 1.

Sample Input

5
1 2 3 4 5
7
1 2 3 4 5 8 8
3
7 5 2

Sample Output

1
6
2