마트료시카 인형

Denisson은 마트료시카 인형을 즐겨 가지고 노는 평범한 애호가이다. 마트료시카 한 세트는 나무 인형으로 이루어져 있다. 이 인형은 가운데에서 위아래로 열리며, 안에서 같은 모양의 더 작은 인형이 나온다. 그 작은 인형 안에는 또 다른 인형이 들어 있고, 이런 식으로 계속된다. 최근 그는 이 장난감 세트를 사서 테이블 위에 어떤 순서로 올려 두었다. 세트에는 크기가 서로 다른 인형이 정확히 $n$개 있으므로, 현재 순서는 길이가 $n$인 순열 $p$로 나타낼 수 있다. 여기서 $p_i$는 $i$번째 인형의 크기이다. 오늘 Denisson은 장난감으로 쉬고 싶어 하며 다음 게임을 한다. 먼저 순열에서 구간 $[l, r]$을 고른다. 그다음 구간에서 가장 작은 마트료시카를 다음 크기의 마트료시카 안에 넣는다. 이 과정에 걸리는 시간은 $|i - j|$이며, 여기서 $p_i$와 $p_j$는 선택한 구간에서 가장 작은 두 인형의 크기이다. 구간에 인형이 하나만 남을 때까지 이 과정을 반복한다. 게임의 총 시간은 모든 과정 시간의 합이다. Denisson은 $q$개의 구간 $[l_i, r_i]$마다 그 구간에서 게임을 하는 데 걸리는 총 시간을 알고 싶어 한다. 그는 여러분이 이 값을 찾는 데 많은 시간을 쓰지 않기를 바란다.

첫째 줄에 마트료시카의 개수 $n$과 요청의 개수 $q$가 주어진다. ($1 \leq n \leq 10^5$, $1 \leq q \leq 5 \cdot 10^5$) 둘째 줄에는 순열 $p$가 주어진다. ($1 \leq p_i \leq n$) 이어지는 $q$개의 줄에는 $i$번째 구간의 양 끝 $l_i$와 $r_i$가 주어진다. ($1 \leq l_i \leq r_i \leq n$)

$i$번째 요청마다 구간 $[l_i, r_i]$에서 게임을 하는 데 걸리는 총 시간을 출력한다.