Problem
最近森に入ったヴァシャは、木の上にケーブルカーを作ることにしました。彼は道をできるだけ長くしたいと思っていますが、森の木々の高さをよく覚えていません。幸いなことに、おそらく 1 本を除いて、すべての木の高さを正確に覚えていると確信しています。
森はn本の木が一列に並んでいて、左から右に1からnまでの番号が付けられていることが知られています。 Vasya によると、i 番目のツリーの高さは hi です。長さ k のケーブルカーは、k (1 <= k <= n) 木 i1, i2, . . . , ik (i1 < i2 < . . < ik) などつまり、hi1 < hi2 < . . . < hik.
Petya も森の中にいて、Vasya がどこで間違っているか正確に推測しています。彼の i 番目の推測は数値 ai と bi によって与えられます。つまり、Petya の意見では、木の高さ
番号 ai は実際には bi と同じです。 Petya の仮定は互いに独立していることに注意してください。
あなたの仕事は、Petya の推測のそれぞれについて、これらの木に基づいて構築できるケーブルカーの最大長を見つけることです.
この問題の枠組みの中で、Vasya はその中の支えとなる木の数を道路の長さと見なしていることに注意してください。
入力データ形式
入力の最初の行には、2 つの数値 n と m (1 <= n, m <= 400 000) が含まれています。それぞれ、森の木の数と Petya の推測の数です。
次の行には n 個の整数 hi (1 <= hi <= 109 ) が含まれます — Vasya の提案による木の高さ。
次の m 行のそれぞれには、2 つの整数 ai と bi が含まれます (1 <= ai <= n, 1 <= bi <= 109 ).
出力形式
Petya の推測ごとに、別の行に 1 つの数字を出力します。ケーブルカーの最大長。
<本体>
|
入る |
出力 |
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 |
注意
最初の例を考えてみましょう。 Petya の最初の仮定は、Vasya の仮定と一致します。
彼の 2 番目の仮定によると、木の高さは (4, 2, 3, 4)、3 番目の仮定では (1, 2, 3, 3)、そして 4 番目の仮定によると — (1、2、3、5)