经验

[赛时答疑](https://www.luogu.org/discuss/show/80694) **简略版已经更新，时限改为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(); } ```