지구 온난화

면접 대비

시간 제한2초메모리 제한512 MB

요약

온도 수열이 주어질 때, 이웃한 값의 차이로 만든 수열에서 마지막 주기가 잘릴 수 있다고 할 때 가장 짧은 주기의 길이를 구한다.

난이도: 쉬움10점 중 3점
유형: 문자열 매칭, 완전 탐색, 구현, 수학
정답자: 아직 제출이 없습니다

문제

과학자들은 지구 온난화의 장기 추세를 예측하려고 합니다. 그들이 검토하는 가설 중 하나는, 아주 긴 기간에 걸쳐 평균 기온이 일정한 주기(cycle) 를 따라 변하되 각 주기가 이전보다 더 높은 기준점에서 시작한다는 것입니다.

기온은 5년 평균값으로 측정되며 0.1도(십분의 일 도) 단위의 정수로 표현됩니다.

이웃한 5년 평균값들 사이의 연속된 차이(difference) 를 생각합니다. 길이 $k$ 의 주기 란 이 차이들이 주기 $k$ 로 반복된다는 뜻입니다. 즉 처음 $k$ 개의 차이가 하나의 패턴을 이루고, 그 뒤의 모든 차이는 $k$ 칸 앞의 차이와 같습니다(마지막 반복은 도중에 잘려도 됩니다).

예를 들어 평균값이

3, 4, 6, 4, 5, 7, 5

이면 차이는 +1, +2, −2, +1, +2, −2 입니다. 길이 3인 패턴 (+1, +2, −2) 가 그대로 반복되므로 가장 짧은 주기의 길이는 3입니다.

또 다른 예로 평균값이

3, 4, 6, 7

이면 차이는 +1, +2, +1 입니다. 길이 2인 패턴 (+1, +2) 가 반복되며 두 번째 반복이 한 원소만 남기고 잘렸으므로 가장 짧은 주기의 길이는 2입니다.

기온의 수열이 주어질 때, 이러한 가장 짧은 주기의 길이를 구하세요.

입력

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 기온의 개수를 나타내는 정수 $n$ ( $1 \le n \le 20$ ) 으로 시작하고, 그 뒤에 $n$ 개의 기온이 이어집니다. 각 기온은 $-1000 \le t \le 1000$ 범위의 정수입니다. 수들은 공백으로 구분됩니다.

$0$ 하나만 있는 줄은 입력의 끝을 나타내며 처리해서는 안 됩니다.

출력

각 테스트 케이스마다 가장 짧은 기온 주기의 길이를 한 줄에 하나씩 출력합니다. 전체 차이 수열 자체를 하나의 긴 주기로 볼 수 있으므로 이러한 주기는 항상 존재합니다.

예제3

예제 1

입력

7 3 4 6 4 5 7 5
3 1 3 5
3 1 4 5
4 3 4 6 7
0

예상 출력

예제 2
입력
```
2 5 8
0
```
예상 출력
```
1
```
예제 3
입력
```
5 2 4 6 8 10
0
```
예상 출력
```
1
```