Play with array

有一个长度为n的数列a₁,a₂,...,a_n。

支持两种操作：

1 l r：将ar移动到al前面。也就是：

        ...,a_l-1,a_l,a_l+1,...a_r,a_r+1,...->...,a_l-1,a_r,a_l,a_l+1,...,a1r-1,a_r+1,...

        这次操作后数列将重新从1到n进行编号。

2 l r k：求a_l,a_l+1,...,a_r中有多少个k。

第一行一个整数n，表示数列长度。

下一行n个整数，表示数列。

下一行一个整数m，表示操作次数。

接下来m行，每行一个操作，格式见题目描述。

对于所有数据，满足1≤n,m≤100000,1≤a_i≤n,1≤l,r,k≤n

以下部分互相独立。

20%的数据，1≤n,m≤1000

20%的数据，1≤n≤3000

20%的数据，1≤n,m≤50000

20%的数据，所有1操作都在2操作之前

对于每一个2操作，输出一行一个数，表示答案。

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

2
1
0
0