Problem
Wir haben eine numerische Sequenz von a1, ..., an . Schreiben Sie ein Programm, das Anfragen der Art " beantwortet;Finden Sie die Länge der größten streng steigenden Untersequenz, alle Elemente
das
-Element befindet sich auf einer Linie mit li-das ri-das ri-Element ist".
ist eine Untersequenz der Sequenz a1 , ..., an wird als Sequenz bezeichnet, die durch Entfernen mehrerer ai -Elemente (die relative Reihenfolge der verbleibenden
) abgerufen werden kann
Elemente dürfen nicht geändert werden). So ist zum Beispiel eine Sequenz (2, 4) eine Untersequenz einer Sequenz (1, 2, 3, 4, 5) ( es ist möglich, die Elemente 1, 3 und 5 ) zu entfernen, und die Sequenz (5, 1) ist dies nicht.
Eingabe
Die ganze Zahl
n ist in der ersten Zeile geschrieben. (1 <= n <= 3000 ) ist die Anzahl der Elemente in der Sequenz. Die zweite Zeile enthält
nvon durch Leerzeichen getrennten Zahlen - die Elemente der Sequenz. Alle Elemente sind Modul 10
9 nicht überlegen. Eine ganze Zahl
q ist in der dritten Zeile geschrieben. (1 <= q <= 10
5) ist die Anzahl der Abfragen. Die folgenden
q-Zeilen beschreiben Abfragen. Beschreibung der
i -Abfrage sind zwei Zahlen
li und
rj (1 <= l
i <= r
i <= n) , die durch ein Leerzeichen geschrieben wurden.
Ausgabe Daten
Geben Sie q von Zahlen aus - Antworten auf Abfragen. Zahlen sollten in derselben Reihenfolge, in der die Abfragen in der Eingabe beschrieben werden, einzeln pro Zeile ausgegeben werden.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
6
3 3 -5 7 4 9
6
1 4
1 2
2 3
1 5
3 5
2 5 |
2
1
1
2
2
2 |