Submit solution
Points:
0.70 (partial)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
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
Comments