Олимпиадный тренинг

Задача 27068. Capybara. cable car


Задача

Темы:
Having recently been in the forest, Vasya decided to build a cable car on the trees. He wants the road to be as long as possible, but he does not remember well the heights of the trees in the forest. Fortunately, he is sure that he remembers the heights of all the trees correctly, except perhaps one of them.

It is known that the forest consists of n trees arranged in a row and numbered from left to right with numbers from 1 to n. The height of the i-th tree, according to Vasya, is hi. A cable car of length k must rest on k (1 <= k <= n) trees i1, i2, . . . , ik (i1 < i2 < . . . < ik), such that their height increases, that is, hi1 < hi2 < . . . < hik.
Petya was also in the forest, and he has q guesses about exactly where Vasya is wrong. His i-th guess is given by the numbers ai and bi , meaning that, in Petya's opinion, the height of the tree
with number ai is actually equal to bi . Please note that Petya's assumptions are independent of each other.

Your task is to find, for each of Petya's guesses, the maximum length of the cable car that can be built based on these trees.
Note that within the framework of this problem, Vasya considers the number of supporting trees in it to be the length of the road.
 
Input data format
The first line of the input contains two numbers n and m (1 <= n, m <= 400 000) — the number of trees in the forest and the number of Petya's guesses, respectively.
The next line contains n integers hi (1 <= hi <= 109 ) — the height of the trees according to Vasya's suggestion.

Each of the next m lines contains two integers ai and bi (1 <= ai <= n, 1 <= bi <= 109 ).

Output format
For each Petya's guess, print on a separate line one number — the maximum length of the cable car.

Enter Output
4 4
1 2 3 4
1 1
14
4 3
4 5
4
3
3
4
4 2
1 3 2 6
3 5
24
4
3
Note
Let's consider the first example. Petya's first assumption coincides with Vasya's.
According to his second assumption, the heights of the trees were (4, 2, 3, 4), the third one (1, 2, 3, 3), and according to the fourth assumption — (1, 2, 3, 5).