Cạo lông hải ly

Cho một hoán vị $a_1,a_2,\dots ,a_n$ của $\{1,2,\dots ,n\}$.

Một đoạn giá trị $[x,y]$ ($1\le x<y\le n$) được gọi là liên tiếp trong hoán vị nếu 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,\dots ,a_{i_k}=y$. Nói cách khác, 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 (không nhất thiết kề nhau).

Nếu không thể xử lý đoạn $[x,y]$ trong một lần, ta chia nó thành các đoạn con $[x,p_1],[p_1+1,p_2],\dots ,[p_m+1,y]$ sao cho mỗi đoạn con là liên tiếp. Khi đó cần $m+1$ lần xử lý. Hãy tìm số lần xử lý tối thiểu cho mỗi truy vấn.

Bạn cần xử lý $q$ truy vấn thuộc hai loại:

• $1xy$ — tính số lần xử lý tối thiểu cho đoạn giá trị $[x,y]$.
• $2xy$ — hoán đổi hai phần tử ở vị trí $x$ và $y$ (tức là $a_x$ và $a_y$).

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên là hoán vị ban đầu $a_1,a_2,\dots ,a_n$.
• Dòng thứ ba chứa số nguyên $q$.
• $q$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $p_i{x}_i{y}_i$ mô tả một truy vấn.

Dữ liệu ra

Với mỗi truy vấn loại $1$, in ra số lần xử lý tối thiểu trên một dòng.

Ràng buộc

• $2\le n\le 3·{10}^5$
• $1\le q\le {10}^5$
• $1\le x_i<y_i\le n$
• $a$ luôn là một hoán vị của $\{1,2,\dots ,n\}$ trong suốt quá trình truy vấn.

Ví dụ