놀이공원 개장을 기다리며

10월 말 토요일 늦은 오전이다. 몇 달에 걸친 개보수를 마친 놀이공원이 그날 오후에 처음으로 문을 연다.

조세와 머리는 정문 옆 사무동 지하에 앉아 있었다. 공원의 모든 놀이기구를 관리하는 인공지능 시스템의 디버깅을 막 끝낸 참이었다. "일은 끝났네." 조세가 말했다. "이제 우리도 좀 놀자. 재미있는 알고리즘 문제 하나 없어?"

"있지." 잡동사니가 쌓인 책상 너머에서 머리가 답했다. "유한한 수열을 생각해 보자. 내가 제일 재미있어하는 건 끝에 긴 등차수열이 붙어 있는 수열이야. 그러니까 어떤 위치에서 시작해 마지막 원소까지 이어지는 등차수열 말이야. 그런 구간은 여러 개일 수 있으니까, 그 수열이 얼마나 재미있는지 알려면 그중 가장 긴 것을 찾아야 해. 자, 수열은 여기 있어. 마지막 원소까지 이어지는 가장 긴 연속 등차 구간이 어디에서 시작하는지 찾아봐."

수열이 등차수열이라는 것은 이웃한 두 원소의 차가 모두 같다는 뜻이다. 원소가 한 개이거나 두 개인 수열은 언제나 등차수열이다.

수열이 주어지면 마지막 원소까지 이어지는 가장 긴 연속 등차 구간의 시작 위치를 구하라.

입력은 여러 개의 테스트 케이스로 이루어지며 파일의 끝까지 이어진다. 각 테스트 케이스는 두 줄이다. 첫째 줄에는 수열의 길이 $N$ ($1 \le N \le 1000$)이 주어진다. 둘째 줄에는 $N$개의 정수 $X_i$ ($0 \le X_i \le 10^9$)가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 한 줄에, 수열의 마지막 원소까지 이어지는 가장 긴 연속 등차 구간의 첫 원소 위치를 출력한다. 수열의 첫 원소 위치는 1이다.