题目背景

赛时答疑

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

攒够经验附魔去~~

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

——图为经验值与等级的关系。

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

题目描述

累积惩罚

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

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

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

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

累计操作数	惩罚
$0$
$1$
$2$	$3$
$3$	$7$
$4$	$15$
$5$	$31$

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

合并物品

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

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

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

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

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

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

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

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

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

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

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

——摘自 mcwiki，稍作删改。

简略版

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

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

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

输入格式

第一行为一个整数 $n$。

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

输出格式

一个整数 $k$，表示 $x$ 在模 $y$ 意义下的乘法逆元，如果没有，请输出 $-1$。

PS：乘法逆元 $k$ 也可以这样理解：$k$ 是使得 $kx \equiv 1 \pmod 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();
}