Amusement Anticipation

It is late Saturday morning at the end of October. The amusement park opens that afternoon for the first time after months of reconstruction.

Josse and Murry were sitting in the basement of the office building by the park gate. They had just finished debugging the AI system that manages every attraction in the park. "Work is done," said Josse. "Now for some amusement. Can you think of an algorithmic problem?"

"Of course," replied Murry from his cluttered desk. "Consider finite sequences of numbers. The ones I find most interesting end with a long arithmetic run, that is, an arithmetic sequence that spans from some position to the very last member. There can be many such runs, so to see how interesting a sequence really is you have to work out which one is the longest. Here is your sequence. Find where the longest contiguous arithmetic run that reaches the end begins."

A sequence is arithmetic when the difference between every pair of neighboring members is the same. A sequence of one or two members is always arithmetic.

Given a sequence, find the position where the longest contiguous arithmetic run ending at the last member starts.

The input holds several test cases and continues to the end of the file. Each test case consists of two lines. The first line contains one integer $N$ ($1 \le N \le 1000$), the length of the sequence. The second line contains $N$ integers $X_i$ ($0 \le X_i \le 10^9$) separated by spaces.

For each test case, print a single line with the position of the first member of the longest contiguous arithmetic run that reaches the end of the sequence. The first member of a sequence is at position 1.