An even number of children are sitting around a round table. Each of them has some number of candies. However, the candies may be distributed unfairly. They decide that in a fair distribution, each of them has exactly the same number of candies as the child sitting at the opposite side of the table.

Your task is to find the optimal number of moves which are required to reach a fair distribution. In one move one child can give one of their candies to an adjacent child. For 1 \le i \le n-1: children numbered i and i+1 are adjacent and children n and 1 are also adjacent. For 1 \le i \le \frac{n}{2}: children numbered i and i+\frac{n}{2} sit at opposite sides of the table.

Input

The first line contains single integer n, the number of children around the table. n is always even.

The second line contains n integers, c_1,c_2,\ldots,c_n, the number of candies each of the children has initially.

Output

Output a single integer, the optimal number of moves. If it is impossible to reach a fair distribution, output QAQ.

Constraints

• 2 \le n \le 10^5
• 0 \le c_k \le 10^9

Examples

Input:

8
4 5 1 7 0 0 3 4

Output:

12

Input:

6
1 2 3 1 1 1

Output:

QAQ

In first example, child 2 gives four candies to child 3 and one candy to child 1. Then child 1 gives all five of their candies to child 8 and child 3 gives two candies to child 4. After the moves, the amounts of candies are: 0 0 3 9 0 0 3 9