Дана последовательность $A_1, A_2, \ldots, A_N$ длины $N$. Все числа в последовательности находятся в диапазоне от $1$ до $N$ и попарно различны. Напишите программу для обработки следующих запросов:

• l r: выведите количество пар целых чисел $(x, y)$ таких, что $l \le x \le y \le r$ и $(max_{i=x}^{y} A_i) - (min_{i=x}^{y} A_i) = y - x$.

Входные данные

Первая строка содержит целое число $N$ — длину последовательности. ($1 \le N \le 120{,}000$)

Вторая строка содержит $N$ целых чисел $A_1, A_2, \ldots, A_N$, все различные. ($1 \le A_i \le N$)

Третья строка содержит целое число $M$ — количество запросов. ($1 \le M \le 120{,}000$)

Следующие $M$ строк содержат каждый запрос в формате l r. ($1 \le l \le r \le N$)

Выходные данные

Для каждого запроса выведите строку, содержащую одно целое число — ответ.

Примеры

Входные данные 1

5
1 3 2 5 4
5
1 1
1 2
1 3
1 4
1 5

Выходные данные 1

1
2
5
6
10