리그전 오브 레전드

최근 최고의 인기를 누리는 인디 게임 "리그 파이트 매니저"는 가상의 게임 "리그전 오브 레전드"의 E-sports 대회인 "리그전 오브 레전드 챔피언스 코리아"의 관리자가 되는 경영 게임이다.

이 대회는 이름답게, 각 팀이 리그전 내의 다른 모든 팀과 정확히 한 번씩 경기를 치르는 방식으로 진행된다. 어떤 두 팀이 경기를 진행할 때, 그 경기의 재미는 두 팀의 인기의 곱과 같다. 또한 리그전의 재미는 그 리그전에서 치르는 모든 경기의 재미의 합이다. 예를 들어 어떤 리그전에 인기가 $1, 2, 3$인 세 팀이 참가했다면, 이 리그전의 재미는 $(1\times2) + (1\times3) + (2\times3) = 11$이 된다.

문제는 이번 대회에 너무 많은 팀이 참여를 원하여, 실력이 비슷한 팀끼리 묶어 각각의 디비전으로 분리하여 대회를 진행하려고 한다. 즉, $l$번째로 잘하는 팀, $l+1$번째로 잘하는 팀, ..., $r$번째로 잘하는 팀을 묶어 하나의 디비전을 만들고, 이 디비전에 참여한 팀끼리 리그전을 진행한다. 한 디비전을 어떻게 구성할지 여러 개의 후보가 주어질 때, 각 후보 디비전의 재미를 구해보자.

첫 번째 줄에 참가를 원하는 팀의 수 $N$($2 \le N \le 100\,000$), 후보 디비전의 개수 $Q$($1 \le Q \le 200\,000$)가 주어진다.

두 번째 줄에 정수 $a_1, a_2, \dots, a_N$이 주어진다. $a_i$는 $i$번째로 잘하는 팀의 인기를 의미한다. ($1 \le a_i \le 1\,000$)

다음 $Q$개의 줄에 걸쳐, 각 후보 디비전을 나타내는 정수 $l$과 $r$ ($1 \le l < r \le N$)이 주어진다. 이것은 $l \le i \le r$를 만족하는 $i$에 대해서, $i$번째로 잘하는 팀들이 전부 리그전에 참가한다는 것을 의미한다.

$Q$개의 줄에 걸쳐 주어진 순서대로, 각 후보 디비전에서 진행되는 리그전의 재미를 출력한다.