Нам дана числовая последовательность a1, ..., an . Напишите программу, отвечающую на запросы вида "найти длину наибольшей строго возрастающей подпоследовательности, все элементы которой находятся на отрезке с li-ого по ri-ый элемент".
Подпоследовательностью последовательности a1 , ..., an называется последовательность, которую можно получить путем удаления нескольких элементов ai (относительный порядок оставшихся элементов менять запрещается). Так, например, последовательность (2, 4) является подпоследовательностью последовательности (1, 2, 3, 4, 5) (можно удалить элементы 1, 3 и 5 ), а последовательность (5, 1) - нет.
Входные данные
В первой строке записано целое число
n (1 <= n <= 3000 ) - число элементов в последовательности. Во второй строке записано
n чисел, разделенных пробелами - элементы последовательности. Все элементы не превосходят по модулю 10
9. В третьей строке записано одно целое число
q (1 <= q <= 10
5) - количество запросов. В следующих
q строках описаны запросы. Описание
i -ого запроса - два числа
li и
rj (1 <= l
i <= r
i <= n) , записанные через пробел.
Выходные данные
Выведите q чисел - ответы на запросы. Числа следует выводить по одному на строке в том же порядке, в котором запросы описаны во вводе.
Примеры
| № |
Входные данные |
Выходные данные |
| 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 |