滑索

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给定长度为 $n$ 的序列 $h$ 和 $m$ 个彼此独立的假设。每个假设给出 $a,b$，表示只在当前假设中把 $h_a$ 改成 $b$。

对每个假设，求修改后序列的最长严格上升子序列长度。每次假设都从原序列开始，不会保留上一次修改。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数 $h_1,h_2,\ldots,h_n$。

接下来 $m$ 行，每行两个整数 $a,b$。

输出格式

输出 $m$ 行，第 $i$ 行表示第 $i$ 个假设下的最长严格上升子序列长度。

样例输入 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

数据范围

$1\le n,m\le4\times10^5$，$1\le h_i,b\le10^9$，$1\le a\le n$。