Codeforces Round 144 (Div. 1) |
---|
Закончено |
У Джона Доу есть кривой забор, состоящий из n прямоугольных досок выстроенных в ряд слева направо: i-тая (1 ≤ i ≤ n) по порядку (слева направо) доска имеет ширину 1 и высоту hi. Будем считать, что i-тая (1 ≤ i ≤ n) по порядку (слева направо) доска имеет номер i.
Кусок забора от l до r (1 ≤ l ≤ r ≤ n) — это последовательность досок с номерами от l до r включительно, то есть, доски с номерами l, l + 1, ..., r. Шириной куска забора от l до r называется величина r - l + 1.
Два куска забора от l1 до r1 и от l2 до r2 называются подходящими, если выполняются следующие условия:
Джон выбрал несколько кусков забора и теперь хочет знать, сколько различных подходящих кусков существует для каждого из них. Два куска забора считаются различными, если существует такая доска, которая принадлежит одному из них и не принадлежит другому.
В первой строке записано целое число n (1 ≤ n ≤ 105) — количество досок в заборе. Во второй строке через пробел записаны n целых чисел h1, h2, ..., hn (1 ≤ hi ≤ 109) — высоты досок забора.
В третьей строке записано целое число q (1 ≤ q ≤ 105) — количество запросов. В следующих q строках через пробел записаны два целых числа li и ri (1 ≤ li ≤ ri ≤ n) — границы i-го куска забора.
Для каждого запроса в отдельной строке выведите целое число — количество кусков забора, подходящих данному. Ответы для запросов выводите в том порядке, в котором запросы заданы во входных данных.
10
1 2 2 1 100 99 99 100 100 100
6
1 4
1 2
3 4
1 5
9 10
10 10
1
2
2
0
2
9
Название |
---|