Problem Description

Steve is always faced with challenges in Minecraft, especially when it comes to repairing enchanted books. Each book has a level denoted by \(a_i\). He has researched the anvil repair and experience mechanisms on the Minecraft Wiki.

Cumulative Penalty:

Every operation on an anvil increases the experience cost due to a "cumulative penalty." For an item never placed on an anvil, the penalty is 0.

Each operation on an anvil (excluding renaming) increases the penalty by multiplying it by 2 and adding 1. After N operations, the penalty is \(2^N - 1\). After 6 operations, the penalty is 63 levels, making further repairs and enchantments impossible in survival mode. After 31 operations, the penalty is 2147483647 levels, making any further operations impossible in any mode.

When merging two items, the player incurs the penalties of both items. The merged item's penalty is calculated based on the higher of the two previous penalties. For example, merging items with penalties of 3 and 15 levels incurs an additional 18 levels of penalty, and the resulting item has a penalty of 31 levels (\(15 \times 2 + 1\)).

Merging Items:

In the anvil interface, the first/left item is the target item, and the second/right item is the sacrificial item, which disappears after merging. If the sacrificial item has enchantments, the anvil attempts to merge them into the target item. The total cost of merging includes:

1. The sum of the cumulative penalties of the target and sacrificial items.
2. Additional renaming costs if applicable.
3. A cost of 2 levels if the target item's durability is not full.
4. Enchantment costs if the sacrificial item has enchantments.
5. No repair cost if the sacrificial item is an enchanted book, but the anvil tries to merge its enchantments into the target item.

Simplified Version:

Given enchanted books, only those of the same level can be merged. The cost of merging is the sum of the cumulative costs of the two books. The resulting book's cumulative cost is twice the maximum cost of the two books plus one. The goal is to achieve the highest possible level of the enchanted book with the minimum cost. Steve, having cheated, has no limit on the highest level.

Given \(n\) enchanted books, each with a level \(a_i\), determine how to achieve the maximum level \(x\) of the enchanted book with the minimum cost \(y\). Assume each book starts with a cumulative penalty of 1.

Steve wants you to write a program to calculate \(x\) and \(y\), but he only requires you to output the multiplicative inverse \(k\) of \(x\) modulo \(y\). If it doesn't exist, output \(-1\).

Input Format

The first line contains an integer \(n\).

The next \(n\) lines each contain an integer \(a_i\), representing the initial level of each enchanted book. The data is not guaranteed to be sorted.

Output Format

Output a single integer \(k\), the multiplicative inverse of \(x\) modulo \(y\). If it doesn't exist, output \(-1\).

Sample Input and Output

Input Sample #1

5
1 1 2 3 4

Output Sample #1

-1

Input Sample #2

4
1 1 1 1

Output Sample #2

7

Notes/Hints

Sample Explanation:

For the first sample:
- Merge two level 1 books, cost 2 experience, penalty becomes 3.
- Merge two level 2 books, cost 4 experience, penalty becomes 7.
- Merge two level 3 books, cost 8 experience, penalty becomes 15.
- Merge two level 4 books, cost 16 experience, penalty becomes 31.

Total experience cost: 2 + 4 + 8 + 16 = 30, maximum level: 5.

For the first sample: \(x = 5\), \(y = 30\).

For the second sample: \(x = 3\), \(y = 10\).

Data Range:

The data is guaranteed to be random, with \(x\), \(y\), and \(k\) within the range of a long int.

Tip:

This problem has a large input, so use fast input methods. Here is a template for fast input (requires including <cctype>):

#include<cctype>
inline void read(int &x){
     char ch=getchar();x=0;
     while(!isdigit(ch))   ch=getchar();
     while(isdigit(ch))   x=x*10+ch-'0',ch=getchar();
}

见题面 Input 部分

见题面 Output 部分