Заяц и медведь
(Время: 3 сек. Память: 128 Мб Сложность: 71%)
Недавно в лесу открылся тренажёрный комплекс, который имеет n залов. Эти залы пронумерованы от 1 до n и расположены в порядке, задаваемом перестановкой p. Между любыми двумя соседними залами, то есть pi и pi+1, существует переход.
Для занятий в комплексе нужно купить один из возможных абонементов, каждый из которых задаётся отрезком [a,b] и стоит b-a+1 монет, где 1 ≤ a ≤ b ≤ n. Такой абонемент позволяет заниматься в залах с номерами от a до b, включительно.
Заяц собрался посещать комплекс, но очень не хочет пересекаться с Медведем, который уже купил абонемент на посещение. Заяц не знает в какое время Медведь будет находиться в залах или в переходах, но точно знает, что при перемещении между залами Медведь не станет тратить время зря, а именно, будет перемещается по наименьшему количеству переходов.
Вам нужно обработать q сценариев, задающихся числами l, r и k: сколько вариантов покупки абонемента есть у Зайца, если он готов заплатить не более k монет, а Медведь приобрёл абонемент [l,r]?
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число n – количество залов в комплексе (1 ≤ n ≤ 2×105).
Вторая строка содержит n целых различных чисел pi (1 ≤ pi ≤ n).
Третья строка содержит целое число q – количество сценариев (1 ≤ q ≤ 3×105).
Каждая из следующих q строк содержит по три целых числа l, r и k (1 ≤ l ≤ r ≤ n; 1 ≤ k ≤ n).
Выходные данные
В выходной файл OUTPUT.TXT для каждого сценария в отдельной строке выведите ответ.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5
1 3 2 4 5
5
1 3 2
2 4 2
2 2 3
3 5 5
1 5 1 | 3
2
5
1
0 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
