Problem
Ayant récemment été dans la forêt, Vasya a décidé de construire un téléphérique sur les arbres. Il veut que la route soit la plus longue possible, mais il ne se souvient pas bien de la hauteur des arbres dans la forêt. Heureusement, il est sûr de se souvenir correctement de la hauteur de tous les arbres, sauf peut-être de l'un d'entre eux.
On sait que la forêt est constituée de n arbres disposés en ligne et numérotés de gauche à droite avec des numéros de 1 à n. La hauteur du i-ème arbre, selon Vasya, est hi. Un téléphérique de longueur k doit reposer sur k (1 <= k <= n) arbres i1, i2, . . . , ik (i1 < i2 < . . . < ik), tel que leur hauteur augmente, c'est-à-dire hi1 < hi2 < . . . < hik.
Petya était également dans la forêt, et il a q deviné exactement où Vasya se trompe. Sa ième supposition est donnée par les nombres ai et bi , ce qui signifie que, selon Petya, la hauteur de l'arbre
avec le nombre ai est en fait égal à bi . Veuillez noter que les hypothèses de Petya sont indépendantes les unes des autres.
Votre tâche est de trouver, pour chacune des suppositions de Petya, la longueur maximale du téléphérique qui peut être construit sur la base de ces arbres.
Notez que dans le cadre de ce problème, Vasya considère que le nombre d'arbres porteurs est la longueur de la route.
Format des données d'entrée
La première ligne de l'entrée contient deux nombres n et m (1 <= n, m <= 400 000) — le nombre d'arbres dans la forêt et le nombre de suppositions de Petya, respectivement.
La ligne suivante contient n entiers hi (1 <= hi <= 109 ) — la hauteur des arbres selon la suggestion de Vasya.
Chacune des m lignes suivantes contient deux entiers ai et bi (1 <= ai <= n, 1 <= bi <= 109 ).
Format de sortie
Pour chaque proposition de Petya, écrivez sur une ligne distincte un chiffre — la longueur maximale du téléphérique.
Entrez
Sortie
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
Remarque
Considérons le premier exemple. La première hypothèse de Petya coïncide avec celle de Vasya.
Selon sa deuxième hypothèse, les hauteurs des arbres étaient (4, 2, 3, 4), la troisième (1, 2, 3, 3), et selon la quatrième hypothèse — (1, 2, 3, 5).