25351번 - 중간 구간 게임

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

중간 구간 게임은 길이 $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$가 구간 내에 동시에 존재해야 한다.

서현이는 게임의 점수가 작아지기 위한 최선의 플레이를 하며, 현서는 게임의 점수가 커지기 위한 최선의 플레이를 한다.

이 게임은 너무나도 재미있어서 설정할 수 있는 구간의 제한을 바꿔가면서 게임을 $T$판 진행하려고 한다! 각 판마다 게임의 점수를 구해보자.

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

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

입력의 다음 $T$번째 줄에는 각 게임에서 설정한 구간의 제한 $L_i, R_i$가 주어진다. 이는 그 게임에서 두 사람이 설정할 수 있는 구간이 $[L_i, R_i]$ 에 포함되어야 한다는 것을 뜻한다.

모든 입력은 정수이다.

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

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