P5032 经验

[赛时答疑](https://www.luogu.org/discuss/show/80694) **简略版已经更新，时限改为 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$|$0$| |$1$|$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$的最小正整数。

### 样例解释 第一个样例： 合并两个第一等级的，合并花费 $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` 范围内。 ### 温馨提示 本题读入量较大，请使用较快的读入方法，在此，提供一种快速读入的样式：（需包含头文件 ``） ```cpp #include 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(); } ```