Giá trị của dãy

Xem dạng PDF

Gửi bài giải

Điểm: 100,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Người đăng:
Nguồn bài:
CF
Dạng bài
Ngôn ngữ cho phép
C++, Pascal, Python

Cho dãy a gồm n phần tử a1,a2,...,an. Gọi a[l..r] là đoạn con có các phần tử ở vị trí từ l đến r (1lrn).

Gọi f(x,l,r) là số lần xuất hiện của phần tử có giá trị là x trong đoạn a[l..r]. Gọi S(l,r) là tập hợp các phần tử phân biệt có trong đoạn a[l..r].

Cho q truy vấn, mỗi truy vấn gồm hai số nguyên dương li,ri (1iq). Hãy tính giá trị của: P(li,ri)=xS(li,ri)(f(x,li,ri)×f(x,li,ri)×x).

Input

  • Dòng đầu tiên chứa hai số nguyên dương n,q;
  • Dòng tiếp theo chứa n số nguyên a1,a2,...,an (1ai106, 1in);
  • q dòng sau, mỗi dòng chứa hai số nguyên li,ri (1lirin, 1iq).

Output

In ra q dòng, dòng thứ i (1iq) là kết quả của P(li,ri).

Scoring

  • Subtask 1 [40%]: n,q1000;
  • Subtask 2 [60%]: n,q105.

Examples

Input
Copy
3 2 
1 2 1 
1 2 
1 3
Output
Copy
3
6

Giải thích:

  • P(1,2)=(1×1×1)+(1×1×2)=3;
  • P(1,3)=(2×2×1)+(1×1×2)=6.