{"code":"dissum","name":"Tổng Riêng Biệt","description":"[user:ami] có một dãy số $A$ gồm $n$ phần tử. Với một dãy số $B$, định nghĩa hàm $F(B)$ chính là số phần tử riêng biệt xuất hiện trong $B$. Hãy tính tổng $F(B)$ với $B$ là một dãy con liên tiếp của $A$.\r\n\r\nNói cách khác, hãy tính tổng $F([A_l, ..., A_r])$ với mọi cặp $1 \\leq l \\leq r \\leq n$.\r\n\r\nVí dụ, $A = [1, 1, 2]$, ta sẽ có:\r\n\r\n- $F([1]) = F([1]) = F([2]) = F([1, 1]) = 1$\r\n- $F([1, 1, 2]) = F([1, 2]) = 2$.\r\n\r\nTổng tất cả các hàm $F$ sẽ là $1 * 4 + 2 * 2 = 8$\r\n\r\nNhiệm vụ của các bạn sẽ khó khăn hơn chút đỉnh. Bây giờ, dãy số sẽ được [user:ami] thay đổi $q$ lần. Mỗi lần, [user:ami] sẽ gán $a[i] = x$. Sau mỗi thay đổi như vậy, các bạn hãy tính tổng $F$ của dãy số $A$ mới.\r\n\r\n

Input

\r\n\r\n- Dòng đầu tiên chứa 1 số nguyên dương $n$ là độ dài dãy $A$.\r\n\r\n- Dòng tiếp theo chứa $n$ số nguyên dương biểu thị dãy $A$.\r\n\r\n- Dòng tiếp theo chứa 1 số nguyên dương $q$ là số truy vấn.\r\n\r\n- $q$ dòng tiếp theo, mỗi dòng chứa một cặp số nguyên dương $i$ $x$ biểu thị một phép gán a[i] = $x$.\r\n\r\n

Output

\r\n\r\n- $q$ dòng, mỗi dòng là một số nguyên dương tương ứng với tổng $F$ của dãy $A$ sau khi thực hiện các biến đổi.\r\n\r\n

Scoring

\r\n\r\nTrong tất cả các test , $1 \\le i \\le N$.\r\n\r\n- Subtask $1$ ($50\\%$ số điểm): $N \\leq 1000$, $x \\le 20, a[i] \\le 20$ và $q = 1$.\r\n\r\n- Subtask $2$ ($20\\%$ số điểm): $N \\leq 10^{5}$, $x \\le 20$, $a[i] \\le 20$ và $q = 1$.\r\n\r\n- Subtask $3$ ($30\\%$ số điểm): $N \\leq 10^{5}$, $x \\le 10^5, a[i] \\le 10^5$ và $q \\le 10^5$.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 4\r\n 1 2 3 4\r\n 3\r\n 1 1\r\n 2 1\r\n 3 1\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 20\r\n 17\r\n 13\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n Sau truy vấn 1, dãy $A$ = [1 2 3 4].\r\n\r\n - F([1]) = F([2]) = F([3]) = F([4]) = 1\r\n - F([1 2]) = F([2 3]) = F([3 4]) = 2\r\n - F([1 2 3]) = F([2 3 4]) = 3\r\n - F([1 2 3 4]) = 4\r\n\r\n Tổng các hàm F sẽ là 1 $ * $ 4 + 2 $ * $ 3 + 3 $ * $ 2 + 4 = 20\r\n\r\n Sau truy vấn 2, dãy $A$ = [1 1 3 4].\r\n\r\n - F([1]) = F([1]) = F([1 1]) = F([3]) = F([4]) = 1\r\n - F([1 3]) = F([3 4]) = F([1 1 3]) = 2\r\n - F([1 1 3 4]) = F([1 3 4]) = 3\r\n\r\n Tổng các hàm F sẽ là 1 $ * $ 5 + 2 $ * $ 3 + 3 $ * $ 2 = 17\r\n\r\n Sau truy vấn 3, dãy $A$ = [1 1 1 4].","points":500.0,"partial":false,"time_limit":2.0,"memory_limit":262144,"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}}