多米诺骨牌
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

        小七在一个数轴上玩多米诺骨牌，她有 n + 2 个多米诺骨牌，每个多米诺骨牌形状相同，均为高 1 个单位长度的长方体。
        她先将两个多米诺骨牌分别放置到 n + 1 和 1 上。接着对于剩下的 n 个多米诺骨牌, 她会将第 i 块多米诺骨牌放置在 a_i + 0.5(1 \leq a_i \leq n，a_i \in N^+) 的位置上，如果该位置已经放置了一个多米诺骨牌，那么小七会将这个多米诺骨牌竖着放在该位置的多米诺骨牌上面（即该位置的多米诺骨牌高度 + 1 ），并与下方多米诺骨牌固定在一起。最后，小七会向左边推倒 n + 1 上的多米诺骨牌。假设x位置上的高为h的多米诺骨牌倒下，那么会使得所有位于[x - h,x]的多米诺骨牌倒下。
        小七的目标是让多米诺骨牌全部倒下。如果不能全部倒下，小七希望修改最少多米诺骨牌的位置，使她的目标能够实现。
        小七会问你m个问题，在第i个问题中，小七想知道将第x_i个多米诺骨牌的位置改为y_i + 0.5后 （这个修改是永久的，1和n + 1位置上的不会被修改），最少需要修改多少多米诺骨牌的位置，使所有多米诺骨牌可以全部倒下。

输入描述:

    第一行输入两个整数 n,m(1 \leq n,m \leq 2 \times 10^5) ，分别表示多米诺骨牌数量和小七的问题数。
    第二行输入 n 个整数 a_1,a_2,\cdots,a_n(1 \leq a_i \leq n)，a_i + 0.5表示第 i 个多米诺骨牌的位置。
    接下来m行，第j行输入两个整数 x_i,y_i(1 \leq x_i,y_i \leq n)表示小七的第 i 个问题中，将第 x_i 个多米诺骨牌的位置改为 y_i + 0.5。

输出描述:

    输出 m 行，第 i 行输出一个整数 ans_i ，表示对小七第 i 个问题的回答。
示例1

输入

复制 
5 3
1 1 3 4 5
1 2
2 5
5 4

输出

复制 
0
1
1

说明

第一次询问中，多米诺骨牌位置变为 2 、 1 、 3 、 4 、 5 。多米诺骨牌可以全部倒下。因此，无需修改。

第二次询问中，多米诺骨牌位置变为 2 、 5 、 3 、 4 、 5 。在这种情况下，至少必须进行一次修改。一个最佳解决方案是将左起第五个多米诺骨牌的位置修改为 2 。

第三次询问中，多米诺骨牌位置变为 2 、 5 、 3 、 4 、 4 。在这种情况下，也必须至少进行一次修改。一个最优解是将左边第三个多米诺骨牌的位置修改为 2 。
示例2

输入

复制 
10 10
8 7 2 9 10 6 6 5 5 4
8 1
6 3
6 2
7 10
9 7
9 9
2 4
8 1
1 8
7 7

输出

复制 
1
0
1
2
2
3
3
3
3
2

备注: