AT_ijpc_training.魔法の訓練 (Magical Training)

いもす是14岁时就进行了魔法觉醒的魔法少女。

いもす为了打倒161天以后即将来临的强敌「ウォーターリークス」，开始进行提高魔力的训练。这个训练是这样的：

一开始，有$N$个魔力值已给出的魔法石排成一列。

现在选择连续的一些魔法石，将它们按照魔力值从小到大排序，也就是说，将魔力值小的魔法石放在较小的编号上这样的训练，可以提高いもす的魔力。每一块魔法石都很重，所以排序的时候只能用魔法交换相邻的两块魔法石。

但是，魔法石有很多，交换魔法石的顺序是相当艰难的。又因为交换的方案有很多，所以いもす选择的是最轻松的方案。而且，魔法石的魔力值会在某些时间点突然发生变化。十分幸运的是，这些变化已经全部被预测了。

为了帮助いもす的魔法训练，请你写一个程序支持如下操作：

题目将给出一个包含$N$个整数的排列$A(A_0…A_{N-1})$，其中从左往右第$i+1$个魔法石的编号为$i$，$A_i$表示$i$号魔法石的魔力值。

要实现的操作如下：

• 含有参数的过程$init(N,A)$:
  • $N$——魔法石的个数。魔法石的编号从左至右依次为$0...N-1$
  • $A$——表示魔法值的整数的序列。保证对$0\le i< N$有$1\le A_i\le N$

           这个过程只在update和train之前出现一次，没有返回值。

• 含有参数的过程$update(i,x)$:
  • $i$——魔力值变动的魔法石编号
  • $x$——魔力变动后魔法石$i$的魔力值。保证$1\le x\le N$

           这个过程被多次调用，一次调用对应一次魔力值的变化，没有返回值。

• 含有参数的过程$train(p,q)$:
  • $p$——选择的魔法石序列的左端魔法石编号。保证$1\le p< N$
  • $q$——选择的魔法石序列的右端魔法石编号。保证$p\le q< N$

           这个过程被多次调用，一次调用对应从魔法石$p$到魔法石$q$（两端也包含），通过更换相邻的魔法石，达到升序排列的训练。需要返回作为对应的训练所需的最小的魔法石交换次数。但是，实际不进行魔法石的交换，只要求交换的次数。

举个例子

当$N=6$时，$A$为$(4,1,2,2,6,5)$时，进行如下的$7$次操作

操作	输出
$train(0, 5)$	$4$
$train(2, 3)$	$0$
$update(1, 5)$	无
$train(0, 5)$	$5$
$train(1, 4)$	$2$
$update(5, 1)$	无
$train(0, 5)$	$9$

数据规模

设$update$和$train$的调用次数为$P,Q$

部分1（12分）

$1\le N\le 100$

$1\le P+Q\le 200$

部分2（18分）

$1\le N\le 5000$

$1\le P+Q\le 10000$

部分3（30分）

$1\le N\le 30000$

$P=0$

$1\le Q\le 20000$

部分4（40分）

$1\le N\le 30000$

$1\le P+Q\le 20000$

第一行包含一个数$N$，表示魔法石总数。

第二行包含$N$个整数$A_0...A_{N-1}$，表示魔法石的魔法值。

第三行包含一个数$M$，表示操作个数。

接下来的$M$行，每行有三个整数$T_i,X_i,Y_i$。$T_i=0$时调用$update(X_i,Y_i)$，$T_i=1$时调用$train(X_i,Y_i)$。

对于每一个$train$操作，输出一行，包含一个数，为最少交换次数。

输入输出样例

输入样例#1

6
4 1 2 2 6 5
7
1 0 5
1 2 3
0 1 5
1 0 5
1 1 4
0 5 1
1 0 5

输出样例#1

4
0
5
2
9