U463908 『凌日潮汐OI』T2 - Luminescence

“亲爱的乘客们，欢迎乘坐本次航班前往‘幸运之地'，目前飞船运行平稳，您可以解开安全带在舱内活动。\ **“翻转个角度思考问题，也许你会有新的发现。”** 本题数据应该无误，因为deepseek独立写出的程序拿了全分

为了使幽蓝边界的破坏力最小化，碎数研准备在日蚀节的烟花上动手脚，他们准备了一个特殊的黄绿色烟花，可以通过乱序算法进行反编译延缓幽蓝边界的传播。\ 但是他们才发现，烟花发射系统是有缺陷的。\ 1、第 $ 1 $ 枚烟花可以任意高度。\ 2、第 $ 2n $ 枚烟花不得高于前一枚的高度，其中 $ n \in N ^ { + } $ 。\ 3、第 $ 2n+1 $ 枚烟花不得低于前一枚的高度，其中 $ n \in N ^ { + } $ 。\ 烟花系统已经准备好了一个长度为 $ N $ 的序列，但是还未确定发射其中的哪些烟花。\ 为了不让集会的管理员发现碎数研的计划，碎数研的成员们控制了烟花发射系统，找了几个点准备选一替换自己的烟花，然后调整了自己烟花的高度，并想知道对应点替换后至多还能发射几枚烟花，这个任务交给了你。\ **注意：碎数研的成员们需要完成自己的使命。**\ 形式化题面：\ 给出序列 $ A $ ，每次改变一个值，**回答问题结束后复原**，改变值之后，选出一个子序列 $ B $ （可以有间隔地挑选），满足： - 序列改变后的值一定要选 - $ \forall n \in N ^ { + } \wedge 2n \le \ | B | , b_{2n} \le b_{2n-1} $ - $ \forall n \in N ^ { + } \wedge 2n+1 \le \ | B | , b_{2n+1} \ge b_{2n} $

第一行 $ 2 $ 个整数 $ N , Q $，表示已经准备好的烟花数量和选定的位置数\ 第二行 $ N $ 个整数，表示先前的烟花序列 $ h _ i $ \ 接下来 $ Q $ 行，每行两个整数 $ a _ i , b _ i $ ，表示询问如果将 $ a_i $ 位置的烟花替换成碎数研的高度为 $ b _ i $ 的烟花，至多能发射多少烟花

共 $ Q $ 行，表示替换后至多能发射的烟花数量

共 $ 10 $ 个数据点\ 对于数据点 $ 1,2 $ ，我们保证 $ N,Q \le 100 $ \ 对于数据点 $ 3 $ ，我们保证 $ N \le 1000 , Q = 1$ \ 对于数据点 $ 4 $ ，我们保证 $ N \le 100 , Q \le 1 \times 10^3 $ \ 对于数据点 $ 5 $ ，我们保证初始序列严格不上升或者严格不下降\ 对于数据的 $ 6 $ ，我们保证 $ Q = 1 $ \ 对于 $ 100 \% $ 的数据，我们保证 $ N,Q \le 1 \times 10^5 $ ，且 $ a _ i , b _ i , h _ i $ 均是不大于 $ 2 \times 10^5 $ 的正整数\ 如果你看不懂样例中的输出 $ 1 $ ，请重新读题