Problem
Essendo stato di recente nella foresta, Vasya ha deciso di costruire una funivia sugli alberi. Vuole che la strada sia la più lunga possibile, ma non ricorda bene l'altezza degli alberi della foresta. Fortunatamente, è sicuro di ricordare correttamente le altezze di tutti gli alberi, tranne forse uno.
È noto che il bosco è costituito da n alberi disposti in fila e numerati da sinistra a destra con numeri da 1 a n. L'altezza dell'i-esimo albero, secondo Vasya, è hi. Una funivia di lunghezza k deve poggiare su k (1 <= k <= n) alberi i1, i2, . . . , ik (i1 < i2 < . . . < ik), tale che la loro altezza aumenta, cioè hi1 < hi2 < . . . < hik.
Anche Petya era nella foresta, e ha indovinato esattamente dove Vasya ha sbagliato. La sua ipotesi i-esima è data dai numeri ai e bi , il che significa che, secondo Petya, l'altezza dell'albero
con numero ai è effettivamente uguale a bi . Tieni presente che le ipotesi di Petya sono indipendenti l'una dall'altra.
Il tuo compito è trovare, per ciascuna ipotesi di Petya, la lunghezza massima della funivia che può essere costruita sulla base di questi alberi.
Si noti che nell'ambito di questo problema, Vasya considera il numero di alberi di supporto in esso come la lunghezza della strada.
Formato dei dati di input
La prima riga dell'input contiene due numeri n e m (1 <= n, m <= 400 000) — il numero di alberi nella foresta e il numero di ipotesi di Petya, rispettivamente.
La riga successiva contiene n numeri interi hi (1 <= hi <= 109 ) — l'altezza degli alberi secondo il suggerimento di Vasya.
Ognuna delle m righe successive contiene due numeri interi ai e bi (1 <= ai <= n, 1 <= bi <= 109 ).
Formato di output
Per ogni ipotesi di Petya, stampa su una riga separata un numero — la lunghezza massima della funivia.
|
Entra |
Uscita |
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
Consideriamo il primo esempio. La prima ipotesi di Petya coincide con quella di Vasya.
Secondo la sua seconda ipotesi, le altezze degli alberi erano (4, 2, 3, 4), la terza (1, 2, 3, 3), e secondo la quarta ipotesi — (1, 2, 3, 5).