Problem
Nachdem er kürzlich im Wald gewesen war, beschloss Vasya, eine Seilbahn auf die Bäume zu bauen. Er möchte, dass die Straße so lang wie möglich ist, aber er kann sich nicht gut an die Höhe der Bäume im Wald erinnern. Zum Glück ist er sich sicher, dass er sich die Höhen aller Bäume richtig erinnert, außer vielleicht einem von ihnen.
Es ist bekannt, dass der Wald aus n Bäumen besteht, die in einer Reihe stehen und von links nach rechts mit Zahlen von 1 bis n nummeriert sind. Die Höhe des i-ten Baumes ist nach Washis Erinnerungen hi. Die Seilbahn der Länge k sollte auf k (1 <= k <= n) der Bäume i1, i2, basieren . . . , ik (i1 < i2 < . . . < ik), so dass ihre Höhe zunimmt, dh hi1 < hi2 < . . . < hik.
Petya war auch im Wald, und er hat q Annahmen darüber, wo Vasya genau falsch liegt. Seine i-e-Vermutung wird durch die Zahlen ai und bi angegeben , was bedeutet, dass Petit die Höhe des Baumes schätzt
mit der Nummer a isti tatsächlich gleich bi . Beachten Sie, dass die Annahmen der Petinas unabhängig sind.
Ihre Aufgabe besteht darin, für jede Petit-Annahme die maximale Länge der Seilbahn zu finden, die mit Unterstützung dieser Bäume gebaut werden kann.
Beachten Sie, dass Vasya im Rahmen dieser Aufgabe die Länge der Straße als die Anzahl der darin befindlichen Stützbäume betrachtet.
Eingabeformat
Die erste Eingabezeile enthält die beiden Zahlen n und m (1 <= n, m <= 400.000), die Anzahl der Bäume in der Gesamtstruktur und die Anzahl der Petit-Annahmen.
Die nächste Zeile enthält n ganze Zahlen hi (1 <= hi <= 109 ) die Baumhöhen werden von Washi angenommen.
Jede der folgenden m Zeilen enthält zwei ganze Zahlen ai und bi (1 <= ai <= n, 1 <= bi <= 109 ).
Ausgabeformat
Geben Sie für jede Petit-Vermutung eine Zahl in einer separaten Zeile aus. die maximale Länge der Seilbahn.
|
Eingabe |
Ausgabe |
4 4
1 2 3 4
1 1
1 4
4 3
4 5 |
4
3
3
4 |
4 2
1 3 2 6
3 5
2 4 |
4
3 |
Bemerkung
Betrachten Sie das erste Beispiel. Die erste Petino-Annahme stimmt mit der von Wasi überein.
Nach seiner zweiten Annahme waren die Baumhöhen (4, 2, 3, 4), dem dritten (1, 2, 3, 3), und nach der vierten Annahme ä (1, 2, 3, 5).