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