리그전 오브 레전드

• $ (\sum_i{a_i})^2 = {\sum_i{a_i^2}} + 2\sum_i\sum_{j>i}{a_ia_j} $ 라는 것만 떠올리면 된다.
• a_i의 누적합과 a_i^2의 누적합을 구해두면, 주어진 쿼리들을 각 O(1)에 처리할수 있다
• 시간복잡도는 O(n+q)

"""Solution code for "BOJ 23327. 리그전 오브 레전드".

- Problem link: https://www.acmicpc.net/problem/23327
- Solution link: http://www.teferi.net/ps/problems/boj/23327

Tags: [prefix sum]
"""

import sys


def main():
    # pylint: disable=unused-variable
    N, Q = [int(x) for x in sys.stdin.readline().split()]
    a = [int(x) for x in sys.stdin.readline().split()]

    prefix_sum = [v := 0] + [v := v + x for x in a]
    prefix_sq_sum = [v := 0] + [v := v + x * x for x in a]

    for _ in range(Q):
        l, r = [int(x) - 1 for x in sys.stdin.readline().split()]

        lr_sum = prefix_sum[r + 1] - prefix_sum[l]
        lr_sq_sum = prefix_sq_sum[r + 1] - prefix_sq_sum[l]
        answer = (lr_sum * lr_sum - lr_sq_sum) // 2

        print(answer)


if __name__ == '__main__':
    main()