CF650D.Zip-line

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 < _i_2 < ... < i__k) such that their heights form an increasing sequence, that is _h__i_1 < _h__i_2 < ... < h__i__k.

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.

瓦西娅决定在附近森林的树上搭建一条滑索。他希望这条滑索尽可能长，但他并不完全记得森林中所有树的确切高度。他确信自己只可能记错其中一棵树的高度，其余树的高度都是正确的。

已知该森林由排成一列的 $n$ 棵树组成，从左到右依次编号为 $1$ 到 $n$。据瓦西娅回忆，第 $i$ 棵树的高度为 $h_i$。一条长度为 $k$ 的滑索需跨越 $k$ 棵树（$1 \le k \le n$），其位置记为 $i_1, i_2, \dots, i_k$（满足 $i_1 < i_2 < \dots < i_k$），且这些树的高度构成严格递增序列，即 $h_{i_1} < h_{i_2} < \dots < h_{i_k}$。

佩佳曾与瓦西娅一同去过这片森林，他现在对瓦西娅给出的高度序列 $h$ 提出了 $q$ 条修正假设。他的第 $i$ 条假设包含两个整数 $a_i$ 和 $b_i$，表示佩佳认为编号为 $a_i$ 的树的实际高度应为 $b_i$。注意：佩佳的每条假设彼此独立。

你的任务是：对每条假设，求出在该假设成立的前提下，能够搭建的滑索的最大长度。

本题中，滑索的长度定义为构成该滑索的树的数量。

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 400 000) — 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 ≤ 109) — 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 ≤ 109).

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 400\,000$），分别表示森林中树的数量以及Petya提出的假设数量。

接下来的一行包含 $n$ 个整数 $h_i$（$1 \leq h_i \leq 10^9$），表示Vasya所记录的各棵树的高度。

接下来的 $m$ 行中，每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i \leq n$，$1 \leq b_i \leq 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.

对于彼得亚的每一条假设，输出一个整数，表示在此假设下可以建造的弹射滑索的最大长度。

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).

考虑第一个样例。第一个假设实际上与瓦西娅记住的高度一致。第二个假设中，各棵树的高度为 $(4,\,2,\,3,\,4)$；第三个假设中为 $(1,\,2,\,3,\,3)$；第四个假设中为 $(1,\,2,\,3,\,5)$。