Cho dãy ~A~ gồm ~N~ phần tử. Các phần tử đánh số từ 1 đến ~N~. Phần tử thứ ~i~ được ký hiệu là ~A(i)~.

Bạn cần thực hiện ~Q~ truy vấn. Với truy vấn thứ ~i~, bạn phải thay đổi giá trị của 1 số trong mảng ~A~ và phải đếm số cặp nghịch thế trong mảng.

1 cặp nghịch thế là 1 cặp ~(i, j)~ thỏa mãn 2 điều kiện sau:

• ~i < j~
• ~A(i) > A(j)~

Ví dụ:

~A = [4, 3, 3, 4]~

Có 2 cặp nghịch thế:

• 1, 2 (đánh số từ 1)
• 1, 3

Input

• Dòng 1: ~N~, với ~1 \le N \le 250,000~.
• Dòng 2: ~N~ số nguyên thể hiện mảng ~A~. ~(1 \le A(i) \le 50,000)~.
• Dòng 3: ~Q~, với ~1 \le Q \le 10,000~.
• ~Q~ dòng tiếp theo, mỗi dòng 2 số ~X~ và ~Y~, thể hiện truy vấn ~A(X) = Y~. ~(1 \le X \le N, 1 \le Y \le 50,000)~.

Output

Với mỗi truy vấn, in ra 1 số duy nhất là số nghịch thế sau khi áp dụng truy vấn đó.

Sample Input

10
2 6 6 4 7 6 3 5 9 1
7
8 8
5 1
5 6
10 5
7 1
10 10
4 6

Sample Output

17
18
16
13
14
8
6