Problem
Tendo estado recentemente na floresta, Vasya decidiu construir um teleférico nas árvores. Ele quer que a estrada seja a mais longa possível, mas não se lembra bem da altura das árvores da floresta. Felizmente, ele tem certeza de que se lembra da altura de todas as árvores corretamente, exceto talvez uma delas.
Sabe-se que a floresta é constituída por n árvores dispostas em fileira e numeradas da esquerda para a direita com números de 1 a n. A altura da i-ésima árvore, de acordo com Vasya, é hi. Um teleférico de comprimento k deve estar apoiado em k (1 <= k <= n) árvores i1, i2, . . . , ik (i1 < i2 < . . . < ik), tal que sua altura aumenta, ou seja, hi1 < hi2 < . . . < hik.
Petya também estava na floresta e tem q palpites sobre exatamente onde Vasya está errado. Seu i-ésimo palpite é dado pelos números ai e bi , o que significa que, na opinião de Petya, a altura da árvore
com o número ai é realmente igual a bi . Observe que as suposições de Petya são independentes umas das outras.
Sua tarefa é encontrar, para cada uma das suposições de Petya, o comprimento máximo do teleférico que pode ser construído com base nessas árvores.
Observe que, dentro da estrutura desse problema, Vasya considera o número de árvores de suporte como sendo o comprimento da estrada.
Formato de dados de entrada
A primeira linha da entrada contém dois números n e m (1 <= n, m <= 400 000) — o número de árvores na floresta e o número de palpites de Petya, respectivamente.
A próxima linha contém n inteiros hi (1 <= hi <= 109 ) — a altura das árvores de acordo com a sugestão de Vasya.
Cada uma das próximas m linhas contém dois inteiros ai e bi (1 <= ai <= n, 1 <= bi <= 109 ).
Formato de saída
Para cada palpite de Petya, imprima em uma linha separada um número — o comprimento máximo do teleférico.
|
Entrar |
Saída |
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
Vamos considerar o primeiro exemplo. A primeira suposição de Petya coincide com a de Vasya.
De acordo com sua segunda suposição, as alturas das árvores eram (4, 2, 3, 4), a terceira (1, 2, 3, 3) e de acordo com a quarta suposição — (1, 2, 3, 5).