Enchantment Book Merging

In Minecraft-like mechanics, every enchantment book has an associated enchantment level and a cumulative penalty. Initially each book has a penalty of 1. You are given n enchantment books; the i-th book has enchantment level \(a_i\). Two books can be merged if and only if they have the same current enchantment level. When you merge two books with penalties \(p_1\) and \(p_2\) (assume \(p_1\le p_2\)), the merge operation:

• Costs \(p_1+p_2\) levels (this cost will be counted toward your total merge cost).
• Produces a new book whose enchantment level increases by 1 (i.e. if both books are of level L, the new book is level \(L+1\)).
• The new book’s cumulative penalty is updated to \(2p_2+1\) (note that since \(p_1\le p_2\) the maximum is \(p_2\)).

You may perform merge operations in any order and you do not need to merge all books. Your objective is twofold:

1. Obtain an enchantment book with the highest possible enchantment level \(x\) (this is your primary goal).
2. Among all strategies that yield a book of level \(x\), minimize the total merge cost \(y\).

Finally, instead of outputting \(x\) and \(y\) directly, you must compute and output the modular multiplicative inverse of \(x\) modulo \(y\), that is, find an integer \(k\) satisfying \[ x\cdot k\equiv 1\pmod{y}, \] or output \(-1\) if such an integer does not exist. Note that if no merge is performed the total cost is defined as 0.

Example Explanation:
For 4 books each of level 1, an optimal strategy is as follows:

• Merge two level 1 books: cost = \(1+1=2\); new book level = 2 with penalty \(2\times1+1=3\).
• Merge the remaining two level 1 books similarly: cost = 2; new book level = 2 with penalty 3.
• Merge the two level 2 books: cost = \(3+3=6\); new book level = 3 with penalty \(2\times3+1=7\).

The total cost is \(2+2+6=10\) and the final enchantment level is \(3\). Since the modular inverse of 3 modulo 10 is 7 (because \(3\times7=21\equiv1\pmod{10}\)), the answer is 7.

inputFormat

The first line contains an integer \(n\) \((1\le n\le10^5)\) representing the number of enchantment books.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) \((1\le a_i\le10^9)\) where \(a_i\) is the enchantment level of the i-th book.

outputFormat

Output a single integer: the modular multiplicative inverse of \(x\) modulo \(y\), where \(x\) is the highest achievable enchantment level and \(y\) is the minimum total cost to achieve that level. If no inverse exists, output \(-1\).

sample

1
3

-1

</p>