The Conductor of the choir is planning to take part in the famous Brazilian Choir Week, and therefore she wants the choir to rehearse a new song, described as follows: • each member of the choir starts singing one note, and only changes the note when determined by the Conductor; • at the end of each bar measure, the Conductor determines that exactly two singers change the note they are singing: one singer starts to sing the note immediately above the note she sang, and another singer starts to sing the note immediately below the note she sang; • the song finishes at the end of the first bar measure in which all singers are singing the same note. The Conductor already has several ideas of how to distribute the notes among choir members at the beginning of the song, in order to create the desired effect. However, she is worried about whether, given a note distribution for the singers, it is possible to reach the end of the song in the way she wants (all singing the same note). And, if that is possible, she wants to know the minimum number of bar measures the song can have. Can you help her? Input The input contains several test cases. The first line of a test case contains an integer N indicating the number of members of the choir. Notes are indicated by integers. The second line contains N integers, indicating the note that each singer must sing at the beginning of the song. Notes are given in non-decreasing order. Output For each test case, print a line containing a single integer indicating the minimum number of bar measures the song can have. If it is not possible to have all members singing the same note, then print the value ‘-1’. Restrictions • 2 ≤ N ≤ 104 • −105 ≤notei ≤105 for0≤i≤N−1 • notei ≤notei+1 for0≤i≤N−2 Sample Input 3 123 4 3 6 9 12 6 1 2 3 4 5 723 5 10 10 10 10 10
2/2 Sample Output 2 -1 601 1