시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB (추가 메모리 없음)148836681.481%

문제

최근 최고의 인기를 누리고 있는 인디 게임 "리그 파이트 매니저"는, 가상의 게임 "리그전 오브 레전드"의 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$개의 줄에 걸쳐 주어진 순서대로, 각 후보 디비전에서 진행되는 리그전의 재미를 출력한다.

예제 입력 1

5 3
5 1 2 3 2
2 4
4 5
1 5

예제 출력 1

11
6
63
  • $l = 2, r = 4$ : 인기가 $[1, 2, 3]$인 세 팀이 리그전에 참가한다. 이 리그전의 재미는 $(1\times2) + (1\times3) + (2\times3) = 11$이 된다.
  • $l = 4, r = 5$ : 인기가 $[3, 2]$인 두 팀이 리그전에 참가한다. 이 리그전의 재미는 $(3\times2) = 6$이 된다.
  • $l = 1, r = 5$ : 인기가 $[5, 1, 2, 3, 2]$인 다섯 팀이 리그전에 참가한다.

출처

University > 홍익대학교 > 2021 홍익대학교 프로그래밍 경진대회 H번