题目背景

赛时答疑

简略版已经更新，时限改为500ms

攒够经验附魔去~~

Steve在minecraft中总是会遇上难题： 他想要修理n本附魔书，每本附魔书的等级为ai，他总是不知道铁砧修理和经验值的机制。他便在mcwiki上搜索到了一些资料：

----图为经验值与等级的关系，摘自mcwiki

他看到这个图，就想：我等级升的越高，我所需要的经验值便越多，那么如果我等级刚好够铁砧修理的话，那我所耗费的经验不就越少了吗？他便继续搜索了下去，并将铁砧机制附在了下面,让你帮他解决问题：

题目描述

累积惩罚：

无论是重命名、修复、还是合并操作，其经验花费都会因其物品先前在铁砧上的操作而增加，这些额外增加的花费被称作“累积惩罚”。对于一件从未放上铁砧的物品，累积惩罚为0。

一个物品每次在铁砧上操作过后（不包括重命名），其累积惩罚都会先乘2再加1。如此一来，一个物品在操作过N次后累积惩罚是2^N-1。6次操作之后，累积惩罚是63级，此时生存模式下无法再作进一步的修复和附魔工作。31次操作后，惩罚等级是2147483647级，此时在任何模式下都不能再进行操作。

当合并两个物品时，玩家会同时受到两件物品的累积惩罚。合并后物品的累积惩罚根据先前两个物品中较高者计算。例如，合并两个累积惩罚分别是3级和15级的物品会额外花费18级的惩罚经验，而合并后的物品惩罚是31级（15*2+1）。

累积惩罚甚至会作用在不会磨损的物品上，譬如附魔书。因此，合并4本时运 I 的附魔书，会得到一本累积惩罚为3的时运 III 附魔书。

 累计操作数	      惩罚

     0	           0

     1	           1

     2	           3

     3	           7

     4	           15

     5	           31

使用合成方格进行的物品修复操作会移除所有累积惩罚，但也会丢失所有的魔咒。

合并物品：

铁砧界面中第一格/左边的物品称为目标物品；第二格/右边的物品称为牺牲物品——合并后会消失。如果牺牲物品附有魔咒，铁砧会同时试图将牺牲物品的附魔合并至目标物品上。无论目标物品上的魔咒是否产生实际变化，铁砧都将根据目标物品与牺牲物品上的魔咒收取玩家的等级耗费。

对于牺牲物品上的每个魔咒来说：如果目标物品也拥有相同的魔咒：

当牺牲物品的魔咒等级较高时，目标物品魔咒的等级将上升至牺牲物品上的等级。

当牺牲物品的魔咒等级相同时，目标物品上魔咒的等级将提升1级，除非其等级已为最高。

当牺牲物品的魔咒等级较低时，目标物品上该魔咒的等级不变。

合并物品的总花费将是下列费用之和：

1.目标物品和牺牲物品的累积惩罚之和。

2.如果同时进行重命名，则额外产生重命名的费用。

3.如果目标物品耐久度未满，则耗费2级用于维修。

4.如果牺牲物品拥有魔咒，则产生附魔费用。

5.如果牺牲物品是一本附魔书，则不会产生维修费用，铁砧会尝试将书本上的魔咒合并至目标物品上。亦可同时对目标物品进行重命名。此时的附魔花费一般会少于合并两个类似物品的费用。

-----摘自mc wiki，稍作删改

简略版：
给出附魔书，只有同等等级的才能合并。合并的代价为两本书的累计代价之和。合成后的书的累计代价为合成前最大代价的2倍加上1。求最高等级和最小花费（要求最高等级为第一关键字）,Steve因为开了挂，所以最高等级不限

现给出$n$本附魔书，每本附魔书有它的等级$ai$,问如何才能得到附魔书的最大等级$x$，在此基础上，请计算合成它消耗的最小等级$y$。（我们假设每本附魔书初始的累积惩罚为1）。

Steve很懒，他不想看上面的话，他只想要让你编写出一个程序计算出$x$与$y$。但Steve为了不外传，他只要求你输出$x$在模$y$意义下的乘法逆元$k$即可。如果没有，请输出$-1$.

输入格式

第一行为一个整数$n$

接下来$n$行，每行均有一个整数$ai$，表示每本附魔书的初始等级，不保证数据有序.

输出格式

一个整数$k$,表示$x$在模$y$意义下的乘法逆元,如果没有，请输出$-1$.
PS：乘法逆元$k$也可以这样理解: $k$是使得 $kx\equiv1(mod$ $y)$的最小正整数

5
1 1 2 3 4

-1

4
1 1 1 1

7

提示

样例解释

第一个样例：
合并两个第一等级的，合并花费2经验，代价升为3
再合并两个第二等级的，花费3+1=4经验，代价升为7
再合并两个第三等级的，花费7+1=8经验，代价升为15
最后合并两个第四等级的，花费15+1=16经验，代价升为31

经验总花费：2+4+8+16=30，最大等级：5

对于第一个样例: $x=5$,$y=30$;

对于第二个样例: $x=3$,$y=10$;

数据范围

保证数据随机，$x$,$y$,$k$在long int范围内

温馨提示

本题读入量较大，请使用较快的读入方法，在此，提供一种快速读入的样式：(需包含头文件<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();
}