Smart Beaver 最近设计并制造了一款创新的纳米技术通用海狸剃须机“Beavershave 5000”。 Beavershave 5000 可以家庭给海狸剃毛!它是如何运作的?很容易!
有n只海狸,每只海狸都有一个从1到n的唯一id。考虑 n 个海狸的排列 a1, a2, ..., an。 Beavershave 5000 需要一次会话来为 id 从 x 到 y(含)的海狸剃毛,当且仅当存在这样的索引 i1 < i2 < ... < ik,即 ai1 = x、ai2 = x + 1、...、aik - 1 = y - 1、aik = y。这真的很方便。例如,它需要一个会话来剃除海狸 1、2、3、...、n 的排列。
如果我们不能在一次会话中将 x 到 y 的海狸剃毛,那么我们可以将这些海狸分为 [x, p1], [p1 + 1, p2], ..., [pm + 1, y] (x ≤ p1 < p2 < ... < pm < y) 组,这样机器就可以在一次会话中为每个组中的海狸剃毛。但是 Beavershave 5000 需要 m + 1 个工作会话才能将海狸从 x 剃到 y。
所有海狸都焦躁不安,不断尝试交换。因此,如果我们更正式地考虑这个问题,我们可以考虑两种类型的查询:
- Beavershave 5000 为 ID 从 x 到 y(含)的海狸剃毛所需的最少会话数是多少?
- 位置 x 和 y 上的两只海狸(海狸 ax 和 ay)交换了。
您可以假设任何海狸都可以被剃毛任意次数。
输入
第一行包含整数 n — 海狸的总数,2 ≤ n。第二行包含 n 个空格分隔的整数——初始海狸排列。
第三行包含整数 q — 查询数,1 ≤ q ≤ 105。接下来的 q 行包含查询。每个查询 i 看起来为 pi xi yi,其中 pi 是查询类型(1 是将海狸从 xi 剃到 yi(含),2 是将海狸位置 xi 和 yi 交换)。所有查询都满足条件:1 ≤ xi < yi ≤ n。
- 要获得 30 分,需要解决具有约束条件的问题:n ≤ 100(子问题 B1);
- 要获得 100 分,您需要解决具有约束条件的问题:n ≤ 3·105(子问题 B1+B2)。
请注意,在子问题 B1 和子问题 B2 中,查询 q 的数量都被限制为 1 ≤ q ≤ 105。
输出
对于 pi = 1 的每个查询,打印 Beavershave 5000 会话的最小数量。
示例
输入 #1
5 1 3 4 2 5 6 1 1 5 1 3 4 2 2 3 1 1 5 2 1 5 1 1 5
输出 #1
2 1 3 5