Phiên xử lý tối thiểu

Cho hoán vị $a_1,a_2,\dots ,a_n$ của các số từ $1$ đến $n$.

Với hai giá trị $x\le y$, ta nói đoạn giá trị $[x,y]$ xử lý được trong một phiên nếu các giá trị $x,x+1,\dots ,y$ xuất hiện trong hoán vị theo đúng thứ tự tăng dần, tức là tồn tại các chỉ số $i_1<i_2<\cdots <i_k$ sao cho $a_{i_1}=x$, $a_{i_2}=x+1$, ..., $a_{i_k}=y$.

Nếu đoạn $[x,y]$ không xử lý được trong một phiên, ta phải chia nó thành các đoạn con liên tiếp $[x,p_1],[p_1+1,p_2],\dots ,[p_m+1,y]$ với $x\le p_1<p_2<\cdots <p_m<y$, sao cho mỗi đoạn con xử lý được trong một phiên. Khi đó cần $m+1$ phiên.

Hãy xử lý $q$ truy vấn thuộc hai loại:

• 1 x y — in ra số phiên tối thiểu cần để xử lý các giá trị từ $x$ đến $y$.
• 2 x y — hoán đổi hai phần tử đang đứng ở vị trí $x$ và vị trí $y$ (tức là đổi chỗ $a_x$ và $a_y$).

Lưu ý ở truy vấn loại $1$ thì $x,y$ là giá trị, còn ở truy vấn loại $2$ thì $x,y$ là vị trí trong hoán vị.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — độ dài hoán vị.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ — hoán vị ban đầu.
• Dòng thứ ba chứa số nguyên $q$ — số truy vấn.
• $q$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $t_i$, $x_i$, $y_i$ mô tả một truy vấn như trên ($t_i\in \{1,2\}$).

Dữ liệu ra

Với mỗi truy vấn loại $1$, in ra trên một dòng số phiên tối thiểu tương ứng.

Ràng buộc

• $2\le n\le 3·{10}^5$
• $a$ là một hoán vị của $1,2,\dots ,n$
• $1\le q\le {10}^5$
• $1\le x_i<y_i\le n$

Ví dụ