Задача №113594. Лука и подмассивы подмассивов
Лука собирается войти в дом Марики, но перед этим ему надо ответить на несколько вопросов о своём массиве из N элементов. Марика задаёт ему Q вопросов, состоящих из чисел L и R . Ему надо сказать, какова длина самого длинного магического подмассива подмассива изначального массива от L до R .
Подмассив называется магическим, если все его элементы лежат между самым левым и самым правым его элементами. Например, массивы [1 3 1 2 4] и [4 1 1 2 1] – магические, а [3 3 4 1] – нет.
В первой строке содержится одно целое число N ( 1 ≤ N ≤ 5·10 5 ), количество элементов в массиве.
Во второй строке содержатся N целых чисел a i ( 1 ≤ a i ≤ 10 9 ).
В третьей строке содержится одно число Q ( 1 ≤ Q ≤ 5·10 5 ), количество запросов.
В полседующих Q строках содержатся по два целых числа L и R , ( 1 ≤ L ≤ R ≤ N ), обозначающих границы подмассива.
В i -й строке вывода должен содежаться ответ на запрос номер i .
50 баллов: N , Q ≤ 3·10 4
5 5 4 3 3 2 3 1 2 1 1 2 4
2 1 3
6 6 6 5 1 6 2 3 4 5 4 6 1 4
2 2 4