{"code":"ltbparray","name":"Giá trị mảng (Trại hè MT&TN 2022)","description":"Cho dãy n số nguyên dương $a_1, a_2, ... , a_n$. Một dãy con $(i,j)$ là dãy $a_i , a_{i+1}, ... , a_j (1 \\le i \\le j \\le n)$.\r\n\r\nVới mỗi số nguyên dương $s$ đặt $K_s$ là số lần $s$ xuất hiện trong dãy con $(i,j)$. Ta định nghĩa giá trị của dãy cọn $(i,j)$ là tổng:\r\n\r\n$$ \\sum_{s \\in N}K^2_s \\times s $$\r\n\r\nYêu cầu: Cho biết trước dãy $a_1, a_2, ... , a_n$. Hãy trả lời $m$ truy vấn, mỗi truy vấn có dạng hai số nguyên $L, R (1 \\le L \\le R \\le n)$ với yêu cầu tính giá trị của dãy con $a_L , a_{L+1}, ... , a_R$\r\n\r\n

Input

\r\n\r\n- Dòng 1: Chứa hai số nguyên dương $n, m (1 \\le n, m \\le 2 \\times 10^5)$\r\n- Dòng 2: Chứa $n$ số nguyên $a_1, a_2, ... , a_n (1 \\le a_i \\le 10^9 )$\r\n- Dòng 3 ...$2+m$: Dòng $2 + i$ chứa hai số nguyên $L_i, R_i (1 \\le L_i, R_i \\le n)$ mô tả truy vấn thứ $i (i = 1 ÷ m)$\r\n\r\n

Output

\r\n\r\n- In ra $m$ dòng, mỗi dòng một số nguyên là kết quả của một truy vấn (theo thứ tự xuất hiện trọng input)\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 3 2\r\n 1 2 1\r\n 1 2\r\n 1 3\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 3\r\n 6\r\n ```\r\n\r\n!!! question \"Test 2\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 8 3\r\n 1 1 2 2 1 3 1 1\r\n 2 7\r\n 1 6\r\n 2 7\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 20\r\n 20\r\n 20\r\n ```","points":300.0,"partial":false,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}