Sức mạnh dãy số
Sức mạnh của dãy số $b_1,b_2,...,b_k$ là tổng các tích $b_i \times b_j$ với $1\le i < j\le k$.
Ví dụ: sức mạnh của dãy (2, -3, 4) được tính = $2\times (-3) + 2\times 4 + (-3)\times 4 = -10$.
Cho dãy $a_1,a_2,..., a_N$. Cho $Q$ truy vấn, hãy tính sức mạnh của dãy $a_L, a_{L+1},...,a_R$.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $N, Q \ (1\le N,Q\le 10^5)$;
- Dòng tiếp theo chứa $N$ số nguyên $a_i \ (|a_i| \le 10^2)$;
- $Q$ dòng tiếp theo, mỗi dòng chứa 2 số nguyên $L, R \ (1\le L\le R\le N)$.
Kết quả
- In trên $Q$ dòng, mỗi dòng chứa kết quả tương ứng cho từng truy vấn.
Chấm điểm
30; $N,Q\le 10^2$. 30; $N,Q\le 10^3$. 40; Không có giới hạn gì thêm.
Ví dụ
Ví dụ 1
input
5 4
1 2 -1 3 7
1 4
3 5
1 2
2 3
output
5
11
2
-2
Comments