Cho dãy ~A~ gồm ~N~ phần tử nguyên dương. Có ~M~ thao tác được thực hiện trên dãy ~A~ có dạng như sau:

• ~X~ ~Y~: Gán ~A_X = Y~, rồi đếm số lượng cặp số nghịch thế tồn tại trong dãy ~A~.

Nhắc lại: Một cặp số nghịch thế trong dãy ~A~ được định nghĩa là một cặp số nguyên ~(i, j)~ sao cho ~1 \leq i < j \leq n~ và ~A_i > A_j~.

Input

• Dòng đầu chứa số nguyên dương ~N~ (~1 \leq N \leq 250000~).
• Dòng thứ ~2~ chứa ~N~ số nguyên dương ~A_i~ cách nhau bởi dấu cách (~A_i \leq 5 \times 10^4~).
• Dòng thứ ~3~ chứa số nguyên dương ~M~ (~M \leq 10^4~).
• ~M~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên dương ~X, Y~ (~X \leq N~ và ~Y \leq 5 \times 10^4~).

Output

Xuất ra ~M~ dòng, dòng thứ ~i~ chứa ~1~ số nguyên duy nhất là đáp án cho truy vấn thứ ~i~.

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