Алиса и Боб живут в отдельных мирах. Как бы сильно они ни стремились общаться, вселенная отвечает лишь равнодушным молчанием. Между их мирами лежит огромная тихая граница, где в ряд стоят $n$ древних врат. Эти врата дремали тысячелетиями, пока однажды, возможно, тронутые желаниями Алисы и Боба, они не начали пробуждаться.

$i$-е врата пробуждаются в день $p_i$. Никакие двое врат не пробуждаются в один и тот же день; таким образом, последовательность $p_1,p_2,\ldots,p_n$ является перестановкой $\{1,2,\ldots,n\}$.

Одни пробужденные врата — это всего лишь одинокая трещина в реальности. Они могут нести мимолетный шепот, но не могут преодолеть пустоту. Чтобы непрерывный отрезок врат образовал истинный путь для Алисы и Боба, в нем должно быть пробуждено хотя бы двое врат. Только тогда пространство между мирами станет достаточно стабильным, чтобы их сообщения могли безопасно пересечь его.

Для любых индексов врат $i

Вам дано $q$ запросов. Каждый запрос задаётся отрезком $[L,R]$. Для каждого запроса вычислите сумму точных дней, когда каждый допустимый непрерывный подотрезок, полностью содержащийся в $[L,R]$, впервые становится способен нести их сообщения:

$$ \sum_{L \le i < j \le R} \operatorname{sec}(i,j). $$

Если $L=R$, то не существует отрезка, содержащего хотя бы двое врат, поэтому ответ равен $0$.

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

Первая строка содержит два целых числа $n$ и $q$ ($1 \le n,q \le 2\cdot 10^5$).

Вторая строка содержит $n$ целых чисел $p_1,p_2,\ldots,p_n$, образующих перестановку $\{1,2,\ldots,n\}$.

Каждая из следующих $q$ строк содержит два целых числа $L$ и $R$ ($1 \le L \le R \le n$), описывающих запрос.

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

Выведите $q$ строк. $t$-я строка должна содержать ответ на $t$-й запрос.

Примеры

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

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

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

18
10
3
0

Примечание

Для первого запроса подотрезки длины не менее $2$ внутри $[1,4]$ имеют вторые минимумы $3,3,2,4,2,4$, поэтому ответ равен $18$.