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 does not remember the heights of all trees in the forest exactly. He is sure that he remembers the correct heights of all trees except, possibly, one of them.

The forest has $n$ trees 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 $h_i$. A zip-line of length $k$ ($1 \le k \le n$) hangs over $k$ trees $i_1, i_2, \ldots, i_k$ ($i_1 < i_2 < \ldots < i_k$) whose heights form an increasing sequence, that is, $h_{i_1} < h_{i_2} < \ldots < h_{i_k}$. The length of a zip-line is the number of trees that form it.

Petya was in the forest with Vasya and has $q$ assumptions about the mistake in Vasya's sequence $h$. His $i$-th assumption consists of two integers $a_i$ and $b_i$, meaning that according to Petya, the height of tree $a_i$ is actually $b_i$. Petya's assumptions are independent of each other.

For each of the $q$ assumptions, find the maximum length of a zip-line that can be built over the trees under that assumption.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 400\,000$), the number of trees and the number of Petya's assumptions. The next line contains $n$ integers $h_i$ ($1 \le h_i \le 10^9$), the heights of the trees according to Vasya. Each of the next $m$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i \le n$, $1 \le b_i \le 10^9$).

For each of Petya's assumptions, output one integer: the maximum length of a zip-line that can be built under that 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)$.