EIU Programming Practices and Exams

Cho trước n số nguyên không âm a1, a2, …, an. Mỗi lần lặp, bạn thay đổi dãy này thành một dãy mới theo cách: phần tử thứ k trong dãy mới bằng trị tuyệt đối của ak -  ak+1. Phần tử cuối cùng sẽ là an – a1. Quá trình lặp sẽ dừng lại khi được một dãy bằng nhau.

Ví dụ với n=4 và bắt đầu với dãy 0  2  5  11 ta sẽ có các lần lặp là:

2  3  6  11

1  3  5  9

2  2  4  8

0  2  4  6

2  2  2  6

0  0  4  4

0  4  0  4

4  4  4  4

Như vậy trong ví dụ này ta sẽ có 8 lần lặp. Hãy viết chương trình các định số lần lặp của một dãy ban đầu

Input

Gồm nhiều bộ test, mỗi bộ test gồm 2 dòng:

• Dòng 1 ghi số n (2<=n<=20)
• Dòng 2 ghi n số của dãy ban đầu

Input kết thúc khi n=0

Output

Với mỗi testcase xuất ra số lần lập trên 1 dòng. Nếu dãy không bằng nhau được sau 1000 lần lặp thì ghi ra dòng -1.

Example

Input:
4
0 2 5 11
5
0 2 5 11 3
4
300 8600 9000 4000
16
12 20 3 7 8 10 44 50 12 200 300 7 8 10 44 50
3
1 1 1
4
0 4 0 4
0

Output:
8
-1
3
50
0
1