Описание

Ограничение по времени: 1000 ms
Ограничение по памяти: 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-ого запроса - два числа li и ri (1 <= li <= ri <= 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 чисел - ответы на запросы. Числа следует выводить по одному на строке в том же порядке, в котором запросы описаны во вводе.


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: