cho.sh

Perfect Choir

Given sorted starting notes for N singers, each measure moves one singer up and another down by one; find the minimum measures until all notes are equal, or -1 if impossible.

Medium7MathGreedyPrefix sumBinary searchInterviewNo attempts yetTime limit2sMemory limit512 MB

Problem

The choir conductor is planning a new song for the Brazilian Choir Week show. The song works like this.

  • Each singer starts on one assigned note and changes note only when the conductor says so.
  • At the end of every measure the conductor tells exactly two singers to change note. One of them moves to the note immediately above the note they were singing, and the other moves to the note immediately below.
  • The song ends at the end of the first measure in which every singer sings the same note.

The length of the song is the number of measures that passed before it ended. If every singer already sings the same note at the start, the song ends at the end of the first measure, so its length is 1.

The conductor already has several plans for handing out the starting notes. What she still wants to know is whether a given assignment can end the way she wants, with every singer on the same note, and if it can, the smallest possible number of measures. Help her out.

Input

The input holds several test cases and continues to the end of the input.

The first line of each test case holds the number of singers NN. The second line holds the NN starting notes, one per singer, in non-decreasing order of pitch. Notes are written as integers, the note immediately above a note is the integer 11 larger, and the note immediately below is the integer 11 smaller.

Constraints

  • 2≤N≤1042 \le N \le 10^4
  • −105≤notai≤105-10^5 \le nota_i \le 10^5 (0≤i≤N−10 \le i \le N - 1)
  • notai≤notai+1nota_i \le nota_{i+1} (0≤i≤N−20 \le i \le N - 2)

Output

For each test case print the smallest possible number of measures on its own line. If the song can never end with every singer on the same note, print −1-1.