앨리스와 밥은 서로 다른 세계에 살고 있다. 아무리 깊이 소통하고 싶어도, 우주는 무관심한 침묵으로만 응답할 뿐이다. 그들의 세계 사이에는 광활하고 고요한 경계가 있으며, 그곳에는 $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

참고

첫 번째 질의의 경우, $[1,4]$ 안에 있는 길이가 $2$ 이상인 부분 배열들의 두 번째 최솟값은 각각 $3,3,2,4,2,4$이므로 답은 $18$이다.