중간 구간 게임

서현과 현서는 중간 구간 게임을 하려고 한다.

이 게임은 길이 $N$인 배열 $A[1 \dots N]$ 위에서 진행된다. 서현이 먼저 $1$ 이상 $N$ 이하인 정수를 하나 정한다. 현서는 서현이 정한 수를 알고 나서, $1$ 이상 $N$ 이하인 정수를 하나 정한다. 두 사람이 정한 수 중 작은 수를 $a$, 큰 수를 $b$라고 하면, 점수는 구간 $[a, b]$에 속하는 중간 원소 $A[k]$의 $k$를 모두 더한 값이다.

원소 $A[i]$가 중간 원소이려면, 구간 안에 $A[j] = A[i]$인 $j < i$가 있고 $A[k] = A[i]$인 $k > i$도 있어야 한다. 같은 값을 가진 원소가 $A[i]$의 왼쪽과 오른쪽에 모두 구간 안에 있어야 한다는 뜻이다.

서현은 점수를 최대한 작게 하려고 하고, 현서는 점수를 최대한 크게 하려고 한다.

두 사람은 이 게임이 재미있어서, 구간의 제한을 바꿔 가며 $T$판을 진행하려고 한다. 각 판의 점수를 구한다.

첫째 줄에 배열의 길이 $N$과 게임의 횟수 $T$가 주어진다.

둘째 줄에는 배열의 원소 $A_1, \dots, A_N$이 공백으로 구분되어 주어진다.

다음 $T$개의 줄에는 각 게임의 구간 제한 $L_i$, $R_i$가 주어진다. 두 사람이 정하는 구간은 $[L_i, R_i]$에 포함되어야 한다. 즉 두 사람은 이 범위 안에서 수를 정해야 한다.

모든 입력은 정수이다.

$T$개의 줄에 걸쳐 각 판의 게임 점수를 출력한다. $i$번째 줄에는 $i$번째 판의 점수를 출력한다.

• $1 \leq N, T \leq 200,000$
• $1 \leq A_i \leq 500,000$
• $1 \leq L_i \leq R_i \leq N$