В компьютерной игре есть
n башен, высота
i-й башни равна
ai метров. Определим расстояние между двумя башнями с индексами
i и
j как
|i−j|. Разрешается прыгнуть с
i-й башни на
j-ю башню тогда и только тогда, когда не существует такого индекса 1 <=
k <=
n, такого, что расстояние от
i-й до
j-й башни не меньше расстояния от
i-й башни до
k-й башни, и
k-я башня имеет большую высоту, чем
j-я. Башня
j достижима из башни
i если существует последовательность корректных прыжков, которая начинается в
i-й башне и заканчивается в
j-й.
Вам даны q запросов вида (u,v,l,r). Для каждого запроса посчитайте количество индексов l <= k <= r, таких, что k-я башня достижима из u-й башни и из v-й башни. Обратите внимание, что во многих подзадачах выполняется ограничение u=v, l=1, r=n, то есть ответом на запрос будет общее число башен, достижимых из u .
Входные данные
Первая строка входных данных содержит одно целое число
n (1 <=
n <= 500000) - количество башен.
Вторая строка входных данных содержит
n чисел
a1,
a2,
...,
an (1 <=
an <= 10
9) - высоты башен.
Третья строка входных данных содержит одно целое число q (1 <= q <= 500000) - количество запросов.
Следующие q строк описывают запросы. i-я из них описывает i-й запрос и содержит четыре целых числа ui, vi, li, ri (1<= ui, vi <= n, 1 <= li <= ri <= n) - индексы вершин запроса и границы отрезка запроса.
Выходные данные
Выведите n чисел, i-е из которых должно быть равным ответу на i-й запрос.
Примечание
В первых двух примерах запросы спрашивают количество достижимых из каждой башни башен.
В первом примере с 1-й башни можно прыгнуть на башни 1 и 5. Любая другая башня имеет меньшую высоту, чем башня 1, поэтому туда нельзя прыгнуть (в качестве k можно выбрать 1). Множество достижимых из 1-й башни также состоит из башен 1 и 5. Со второй башни можно прыгнуть на башни 1, 2, и 5, они же являются множеством достижимых. С третьей башни можно прыгнуть на башни 2, 3, 5. Однако, башня 1 также является достижимой, поскольку можно сделать два прыжка: 3→2→1. Таким образом, получается 4 достижимые башни. С 4-й башни можно прыгнуть на башни 4 и 5, они же являются единственными достижимыми. Из 5-й башни достижима только она сама.
Во втором примере из 1-й и из 2-й башни достижимы башни 1,2,3,4,5. Из 3-й башни достижимы башни 3,4,5. Из 4-й и 5-й башни достижимы башни 4,5. Из 6-й башни достижимы башни 4,5,6. Из 7-й башни достижимы башни 4,5,6,7.
Рассмотрим третий пример:
- В первом запросе множество индексов башен k на отрезке [l,r], достижимых из u и из v — {3,6}.
- Во втором запросе множество индексов башен k на отрезке [l,r], достижимых из u и из v — {6}.
- В третьем запросе множество индексов башен k на отрезке [l,r], достижимых из u и из v — {3}.
- В четвёртом запросе множество индексов башен k на отрезке [l,r], достижимых из u и из v пусто.
- В пятом запросе множество индексов башен k на отрезке [l,r], достижимых из u и из v — {6}.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
7 6 3 4 10
5
1 1 1 5
2 2 1 5
3 3 1 5
4 4 1 5
5 5 1 5
|
2
3
4
2
1
|
| 2 |
7
1 1 1 2 2 1 1
7
1 1 1 7
2 2 1 7
3 3 1 7
4 4 1 7
5 5 1 7
6 6 1 7
7 7 1 7
|
5
5
3
2
2
3
4
|
| 3 |
7
6 8 9 3 5 10 1
5
1 3 2 7
4 5 1 6
1 4 2 4
4 7 1 3
1 5 3 6
|
2
1
1
0
1
|