Zip-line

题意翻译

\$\$ #### 题目大意： 给定一个长度为$n$的序列以及$m$个操作，每个操作形如“$a_i~b_i$”，表示将序列中第$a_i$个数改为$b_i$。 对于每个操作，求出序列的最长严格上升子序列长度。 **注意：每个操作之间彼此独立。（即每次操作未进行时的序列是输入时的原序列，而不是上一次操作后得到的序列）** #### 输入格式： 第一行输入两个数$n$和$m$； 第二行输入$n$个数，表示原序列； 接下来$m$行，每行输入两个数$a_i~b_i$意义如上所述。 #### 输出格式： 共$m$行，每行一个数，为当前操作之后的最长严格上升子序列的长度。

题目描述

Vasya has decided to build a zip-line on trees of a nearby forest. He wants the line to be as long as possible but he doesn't remember exactly the heights of all trees in the forest. He is sure that he remembers correct heights of all trees except, possibly, one of them. It is known that the forest consists of $ n $ trees staying in a row numbered from left to right with integers from $ 1 $ to $ n $ . According to Vasya, the height of the $ i $ -th tree is equal to $ h_{i} $ . The zip-line of length $ k $ should hang over $ k $ ( $ 1<=k<=n $ ) trees $ i_{1},i_{2},...,i_{k} $ ( $ i_{1}&lt;i_{2}&lt;...&lt;i_{k} $ ) such that their heights form an increasing sequence, that is $ h_{i1}&lt;h_{i2}&lt;...&lt;h_{ik} $ . Petya had been in this forest together with Vasya, and he now has $ q $ assumptions about the mistake in Vasya's sequence $ h $ . His $ i $ -th assumption consists of two integers $ a_{i} $ and $ b_{i} $ indicating that, according to Petya, the height of the tree numbered $ a_{i} $ is actually equal to $ b_{i} $ . Note that Petya's assumptions are independent from each other. Your task is to find the maximum length of a zip-line that can be built over the trees under each of the $ q $ assumptions. In this problem the length of a zip line is considered equal to the number of trees that form this zip-line.

输入输出格式

输入格式

The first line of the input contains two integers $ n $ and $ m $ ( $ 1<=n,m<=400000 $ ) — the number of the trees in the forest and the number of Petya's assumptions, respectively. The following line contains $ n $ integers $ h_{i} $ ( $ 1<=h_{i}<=10^{9} $ ) — the heights of trees according to Vasya. Each of the following $ m $ lines contains two integers $ a_{i} $ and $ b_{i} $ ( $ 1<=a_{i}<=n $ , $ 1<=b_{i}<=10^{9} $ ).

输出格式

For each of the Petya's assumptions output one integer, indicating the maximum length of a zip-line that can be built under this assumption.

输入输出样例

输入样例 #1

4 4
1 2 3 4
1 1
1 4
4 3
4 5

输出样例 #1

4
3
3
4

输入样例 #2

4 2
1 3 2 6
3 5
2 4

输出样例 #2

4
3

说明

Consider the first sample. The first assumption actually coincides with the height remembered by Vasya. In the second assumption the heights of the trees are $ (4,2,3,4) $ , in the third one they are $ (1,2,3,3) $ and in the fourth one they are $ (1,2,3,5) $ .