P8919 『MdOI R5』Message

小 A 有一个群。这个群正在玩一个小游戏：给出一个函数 $f$，从某一个时间点起，发送第 $x$ 条消息，而 $f(x)=1$ 的群友会受到一个小惩罚。当群内消息总数达到 $m$ 时游戏结束。 但小 A 是个话痨，这段时间他在这个群发了 $n$ 条消息，他发的第 $i$ 条消息在整个消息记录里是第 $a_i$ 条消息。 但是小 A 不想受到惩罚，而小 A 恰好是管理员，他可以撤回**任何时刻、任何群成员发的任何消息**，注意这会导致这条消息之后的消息排名改变。 但是撤回消息太多容易被当成暴政，因此他要尽可能减少撤回信息次数，不管是自己的还是别人的。 接下来你也猜到你要干什么了：假如其他群成员不操作，给出 $n$、函数 $f$ 和 $a_i$，求出他至少要撤回几条消息。

无

无

【样例解释】 下面给出一种可能的方式： - 小 A 先撤回第 $1$ 条消息（群友发的），他的四条消息在消息记录里现在是第 $1,5,7,10$ 条。 - 然后撤回第 $5$ 条消息（他自己发的），剩下三条消息在消息记录里现在是第 $1,6,9$ 条。 此时三条消息满足 $f(1)=f(6)=f(9)=0$，符合题意。 可以证明无法仅撤回一条消息达成要求。 【数据范围】 |Subtask|$n\le$|$m\le$|特殊性质|分值| |:-:|:-:|:-:|:-:|:-:| |1|$17$|$17$||$15$| |2|$17$|$100$||$15$| |3|$10^3$|$10^4$||$20$| |4||$10^5$|$n=m$|$8$| |5|$10^5$|$10^6$|A|$12$| |6|$10^5$|$10^6$||$30$| - 特殊性质 A：小 A 没有连发两条消息。 对于全部数据，$1\le n\le 10^5$，$1\le a_i\le m\le 10^6$，$a_i$ 严格递增，$f(i)\in \{0,1\}$。