#P18106. Jaded Juice

Jaded Juice

Jaded Juice

Lupa 有 nn 个普通透明瓶和一个特殊透明瓶。普通瓶的高度都是 ww,瓶底位于高度 00,瓶口位于高度 ww;特殊瓶的高度为 2w2w。

最初,所有瓶子的果汁都达到同一个未知的整数高度 xx,其中 0≤x≤w0\le x\le w。

第 ii 个普通瓶的深色标签遮住高度从 lil_i 到 ww 的部分。因此,只有果汁高度严格小于 lil_i 时,Lupa 才能看清这个瓶子的果汁高度。

特殊瓶的标签遮住高度从 00 到 ww 的部分。因此,只有果汁高度严格大于 ww 时,Lupa 才能看清特殊瓶的果汁高度。

一次操作中,Lupa 选择一个普通瓶和一个非负整数 pp,从这个普通瓶向特殊瓶倒入恰好 pp 单位的果汁。每次操作后,她会观察所有能看见的果汁高度。倒出或倒入 pp 单位果汁,相应瓶子的果汁高度分别下降或上升 pp。

Lupa 不能执行可能无法完成的操作:在选择一次倒水前,考虑所有与此前观察结果相符的 xx。对于其中每一个可能的 xx,被选的普通瓶里都必须至少有 pp 单位的果汁,这次操作才合法。

她可以根据此前的观察结果调整之后的策略,并在能够唯一确定 xx 时立即停止。最初不进行操作时,如果已有可见水位,也能直接确定 xx。

求最少需要多少次操作,才能保证无论初始隐藏高度 xx 是多少,都能确定它。

输入格式

第一行包含两个整数 n,wn,w,其中 1≤n≤1061\le n\le10^6,2≤w≤10182\le w\le10^{18}。

第二行包含 nn 个整数 l1,l2,…,lnl_1,l_2,\ldots,l_n,其中 1≤li<w1\le l_i<w。

输出格式

输出一个整数,表示保证确定 xx 所需的最少操作次数。

样例

输入:

3 34
1 2 4

输出:

3

样例解释

如果 x<4x<4,初始时就能从标签为 44 的瓶子看到水位。否则,目前 4≤x≤344\le x\le34。

先从标签为 44 的瓶子倒出 44 单位。若 x<8x<8,普通瓶会露出水位;若 x>30x>30,特殊瓶会露出水位。尚未确定的情况因此只剩 8≤x≤308\le x\le30。

再从同一瓶倒出 44 单位。尚未确定的情况变为 12≤x≤2612\le x\le26。

最后从标签为 22 的瓶子倒出 1212 单位。若 x<14x<14,这个普通瓶露出水位;若 x>14x>14,特殊瓶露出水位;否则只有 x=14x=14 这一种可能。因此三次操作足够。