CF331B1 Shave Beaver!

一位聪明的海狸最近发明了一种新型的纳米技术多功能海狸剃毛机「Beavershave 5000」，它能为整家族的海狸剃毛！这台机器是如何工作的呢？真是简单极了！ 现有 $n$ 只海狸，每只海狸都有一个从 1 到 $n$ 的唯一编号。设想一个由这些海狸编号组成的排列 $a_1, a_2, \ldots, a_n$。如果存在一串下标 $i_1 < i_2 < \ldots < i_k$，使得 $a_{i1} = x$，$a_{i2} = x+1$，一直到 $a_{ik-1} = y-1$，$a_{ik} = y$，那么 Beavershave 5000 就可以在一次会话中为从编号 $x$ 到 $y$ 的海狸剃毛。例如，对排列 $1, 2, 3, \ldots, n$ 的海狸来说，只需要一次会话。 如果无法用一次会话剃掉编号从 $x$ 到 $y$ 的海狸，海狸们可以被分成若干组：$[x, p_1]$，$[p_1+1, p_2]$，……，$[p_m+1, y]$（$x \leq p_1 < p_2 < \ldots < p_m < y$），这样机器就可以在每组内一次完成剃毛。但此时 Beavershave 5000 总共需要 $m+1$ 次会话来处理从 $x$ 到 $y$ 的海狸。 这些海狸常常不安分，总是在尝试交换位置。因此，我们会遇到以下两类查询： - 查询 Beavershave 5000 需要多少次会话才能完成编号从 $x$ 到 $y$ 的海狸的剃毛任务？ - 查询交换位置 $x$ 和 $y$ 上海狸（即交换 $a_x$ 和 $a_y$）。 可以假设任何一只海狸可以多次被剃毛。

第一行包含一个整数 $n$，表示海狸的总数，满足 $2 \leq n$。第二行包含 $n$ 个用空格分隔的整数，表示海狸的初始排列。 第三行包含一个整数 $q$，表示查询的数量，满足 $1 \leq q \leq 10^5$。接下来的 $q$ 行，每行为一个查询，形式为 $p_i$ $x_i$ $y_i$，其中 $p_i$ 是查询类型（$1$ 表示剃毛，$2$ 表示交换位置）。所有查询满足条件：$1 \leq x_i < y_i \leq n$。 - 为了获得 30 分，你需要解决以下约束条件：$n \leq 100$（子问题 B1）； - 为了获得 100 分，你需要解决以下约束条件：$n \leq 3 \cdot 10^5$（子问题 B1+B2）。 请注意，在子问题 B1 和 B2 中，查询数量 $q$ 的限制都是 $1 \leq q \leq 10^5$。

对于每个 $p_i = 1$ 的查询，输出 Beavershave 5000 所需的最少会话次数。 **本翻译由 AI 自动生成**