Problem
Habiendo estado recientemente en el bosque, Vasya decidió construir un teleférico en los árboles. Quiere que el camino sea lo más largo posible, pero no recuerda bien las alturas de los árboles del bosque. Afortunadamente, está seguro de recordar correctamente la altura de todos los árboles, excepto quizás uno de ellos.
Se sabe que el bosque está formado por n árboles dispuestos en fila y numerados de izquierda a derecha con números del 1 al n. La altura del i-ésimo árbol, según Vasya, es hi. Un teleférico de longitud k debe descansar sobre k (1 <= k <= n) árboles i1, i2, . . . , ik (i1 < i2 < . . . < ik), tal que su altura aumenta, es decir, hi1 < hi2 < . . . < hik.
Petya también estaba en el bosque, y tiene q conjeturas acerca de exactamente dónde se equivocó Vasya. Su i-ésima suposición está dada por los números ai y bi , lo que significa que, en opinión de Petya, la altura del árbol
con el número ai es en realidad igual a bi . Tenga en cuenta que las suposiciones de Petya son independientes entre sí.
Tu tarea es encontrar, para cada una de las conjeturas de Petya, la longitud máxima del teleférico que se puede construir sobre la base de estos árboles.
Tenga en cuenta que, en el marco de este problema, Vasya considera que el número de árboles de apoyo es la longitud del camino.
Formato de datos de entrada
La primera línea de la entrada contiene dos números n y m (1 <= n, m <= 400 000) — el número de árboles en el bosque y el número de conjeturas de Petya, respectivamente.
La siguiente línea contiene n enteros hi (1 <= hi <= 109 ) — la altura de los árboles según la sugerencia de Vasya.
Cada una de las siguientes m líneas contiene dos números enteros ai y bi (1 <= ai <= n, 1 <= bi <= 109 ).
Formato de salida
Para cada suposición de Petya, escriba en una línea separada un número — la longitud máxima del teleférico.
|
Entrar |
Salida |
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 |
Nota
Consideremos el primer ejemplo. La primera suposición de Petya coincide con la de Vasya.
Según su segunda suposición, las alturas de los árboles eran (4, 2, 3, 4), la tercera (1, 2, 3, 3), y según la cuarta suposición — (1, 2, 3, 5).