#3787. Gty的文艺妹子序列

内存限制:256 MiB 时间限制:50 Sec

题目描述

Autumn终于会求区间逆序对了!Bakser神犇决定再考验一下他,他说道:
“在Gty的妹子序列里,某个妹子的美丽度可也是会变化的呢。你还能求出某个区间
中妹子们美丽度的逆序对数吗?当然,为了方便,这次我们规定妹子们的美丽度在
[1,n]中。仍然强制在线。”
Autumn需要你的帮助。
给定一个正整数序列a(1<=ai<=n),支持单点修改,对于每次询问,输出al...ar中
的逆序对数,强制在线。

输入格式

第一行包括一个整数n(1<=n<=50000),表示数列a中的元素数。
第二行包括n个整数a1...an(1<=ai<=n)。
接下来一行包括一个整数m(1<=m<=50000),表示操作的个数。
接下来m行,每行包括3个整数。
0 L R (1<=L<=R<=n) 询问[L,R]中的逆序对数。
1 p v (1<=p<=n,1<=v<=n) 将p位置的数修改为v。
L,R,p,v 都需要异或上一次的答案,保证异或之后的值是合法的。
保证涉及的所有数在int内。

输出格式

对每个询问,单独输出一行,表示al...ar中的逆序对数。对每个询问,单独输出一行,表示al...ar中的逆序对数。

样例

样例输入


			
10
1 7 5 6 9 4 9 4 4 7
10
0 4 6
0 5 8
0 1 10
1 25 19
0 19 25
1 14 4
0 12 12
0 2 5
1 8 7
1 1 10

样例输出


			
2
3
16
13
0
2

数据范围与提示