Global Warming

Interview

Time limit2sMemory limit512 MB

Summary

Given a sequence of temperatures, find the length of the shortest period of the sequence of consecutive differences, allowing the final repetition to be truncated.

Level: Easy3 of 10
Topics: String matching, Brute force, Implementation, Math
Solved: No attempts yet

Problem

Scientists want to predict the long-term trend of global warming. One hypothesis they are considering is that, over very long time spans, the average temperature follows a repeating cycle, but each cycle starts from a higher baseline than the previous one.

Temperatures are measured as five-year averages and expressed as integers in tenths of a degree.

Consider the consecutive differences between neighboring five-year averages. A cycle of length $k$ means these differences repeat with period $k$ : the first $k$ differences form a pattern, and every later difference equals the one $k$ positions earlier (the final repetition of the pattern may be truncated).

For example, from the averages

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

the differences are +1, +2, −2, +1, +2, −2. The pattern (+1, +2, −2) of length 3 repeats exactly, so the shortest cycle has length 3.

As another example, from the averages

3, 4, 6, 7

the differences are +1, +2, +1. The pattern (+1, +2) of length 2 repeats, with the second repetition truncated after a single element, so the shortest cycle has length 2.

Given a sequence of temperatures, find the length of the shortest such cycle.

Input

The input consists of several test cases. Each test case begins with an integer $n$ ( $1 \le n \le 20$ ), the number of temperatures, followed by the $n$ temperatures themselves. Each temperature is an integer with $-1000 \le t \le 1000$ . Numbers are separated by whitespace.

A line containing a single $0$ marks the end of the input and must not be processed.

Output

For each test case, output on its own line the length of the shortest temperature cycle. Such a cycle always exists, because the entire sequence of differences can be treated as one long cycle.

Examples3

Example 1

Input

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

Expected output

Example 2
Input
```
2 5 8
0
```
Expected output
```
1
```
Example 3
Input
```
5 2 4 6 8 10
0
```
Expected output
```
1
```