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\).

Nó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\).

Ví dụ, \(A = [1, 1, 2]\), ta sẽ có:

• \(F([1]) = F([1]) = F([2]) = F([1, 1]) = 1\)
• \(F([1, 1, 2]) = F([1, 2]) = 2\).

Tổng tất cả các hàm \(F\) sẽ là \(1 * 4 + 2 * 2 = 8\)

Nhiệ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 ami thay đổi \(q\) lần. Mỗi lần, 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.

Input

• Dòng đầu tiên chứa 1 số nguyên dương \(n\) là độ dài dãy \(A\).

• Dòng tiếp theo chứa \(n\) số nguyên dương biểu thị dãy \(A\).

• Dòng tiếp theo chứa 1 số nguyên dương \(q\) là số truy vấ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\).

Output

• \(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.

Scoring

Trong tất cả các test , \(1 \le i \le N\).

• Subtask \(1\) (\(50\%\) số điểm): \(N \leq 1000\), \(x \le 20, a[i] \le 20\) và \(q = 1\).

• Subtask \(2\) (\(20\%\) số điểm): \(N \leq 10^{5}\), \(x \le 20\), \(a[i] \le 20\) và \(q = 1\).

• Subtask \(3\) (\(30\%\) số điểm): \(N \leq 10^{5}\), \(x \le 10^5, a[i] \le 10^5\) và \(q \le 10^5\).

Example

4
1 2 3 4
3
1 1
2 1
3 1

20
17
13