Description

Autumn终于会求区间逆序对了!Bakser神犇决定再考验一下他，他说道：

“在Gty的妹子序列里，某个妹子的美丽度可也是会变化的呢。你还能求出某个区间

中妹子们美丽度的逆序对数吗？当然，为了方便，这次我们规定妹子们的美丽度在

[1,n]中。仍然强制在线。”

Autumn需要你的帮助。

给定一个正整数序列a(1<=ai<=n)，支持单点修改，对于每次询问，输出al...ar中

的逆序对数，强制在线。

Format

Input

第一行包括一个整数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内。

Output

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

Samples

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

Limitation