A Math Contest P10 - Tricky Multisets

View as PDF

Submit solution

Points: 12
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem types

You are given a multiset S. Each element in the multiset is an integer between -N and N (inclusive), where i appears a_i times in the multiset.

In each operation, you choose two different elements of the multiset, X and Y, such that |X-Y| = 2. Then, X and Y will be deleted from the multiset, and \frac{X+Y}{2} will be added to the multiset twice.

Find the minimum number of operations such that every element of S is equal to 0. The data guarantees that such a sequence of operations will exist.

Constraints

1 \le N \le 5 \times 10^5

0 \le \sum a_i \le 10^{18}

Input Specification

The first line contains an integer, N.

The next line contains 2N+1 integers, a_{-N}, a_{-N+1}, \dots, a_N.

Output Specification

Output the minimum number of operations to set all elements to 0 modulo 10^9+7.

Sample Input

2
1 1 1 1 1

Sample Output

5

Explanation for Sample

Let's keep track of the elements in the multiset after each operation.

Initially, the multiset has the elements \{-2, -1, 0, 1, 2\} within it.

  1. Choose X = 2 and Y = 0 : \{-2, -1, 1, 1, 1\}
  2. Choose X = 1 and Y = -1 : \{-2, 0, 0, 1, 1\}
  3. Choose X = -2 and Y = 0 : \{-1, -1, 0, 1, 1\}
  4. Choose X = -1 and Y = 1 : \{-1, 0, 0, 0, 1\}
  5. Choose X = -1 and Y = 1 : \{0, 0, 0, 0, 0\}

It can be proven that 5 is the minimum number of operations required to set everything to 0.


Comments

There are no comments at the moment.