Задача: Башни 3.0

В компьютерной игре есть 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 .

Третья строка входных данных содержит одно целое число q (1 <= q  <= 500000) - количество запросов.

Следующие q строк описывают запросы. i-я из них описывает i-й запрос и содержит четыре целых числа ui, vi, li, ri (1<= u_i, v_i <= n, 1 <= l_i <= r_i <= 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}.

Примеры

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

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

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

Ваш ответ: