Czech ACM Student Chapter

Czech Technical University in Prague

Charles University in Prague

Technical University of Ostrava

ˇ

Slovak University of Technology

University of Zilina

Masaryk University

University of West Bohemia

CTU Open Contest 2017

Amusement Anticipation

amusement.c, amusement.cpp, amusement.c11, Amusement.java, amusement.py

It is 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. "Con-

sider, 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 ≤ N ≤ 1 000) specifying the length of the sequence. The second line contains a sequence of

N integers Xi (0 ≤ Xi ≤ 109 ), 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

Output for Sample Input

5

1

12345

6

7

2

1234588

3

752