Xét dãy số nguyên ~a_1~, ~a_2~,..., ~a_n~, các số nhận giá trị không vượt quá ~n~ và khác nhau từng đôi một.

Yêu cầu xử lý ~m~ truy vấn, mỗi truy vấn có một trong 2 dạng:

• ~1~ ~p~ ~q~ - đổi chỗ 2 số trong dãy ở các vị trí ~p~ và ~q~ cho nhau,
• ~2~ ~p~ ~q~ - kiểm tra các số của dãy ở các vị trí thuộc đoạn ~[p, q]~ có phủ kín các điểm tọa độ nguyên của một đoạn thẳng nào đó hay không, nói một cách khác, có tồn tại số nguyên ~r~ để các số ~r, r+1,..., r+q-p~ thuộc đoạn ~[p, q]~ của dãy và đưa ra kết quả "YES" hoặc "NO" tương ứng (kết quả có phân biệt hoa thường).

Input

Dòng đầu tiên chứa một số nguyên ~n~ ~(1 \le n \le 10^5)~,

Dòng thứ 2 chứa n số nguyên ~a_1, a_2,..., a_n~ ~(|a_i| \le n)~,

Dòng thứ 3 chứa số nguyên ~m~ ~(1 \le m \le 10^5)~,

Mỗi dòng trong ~m~ dòng tiếp theo chứa 3 số nguyên xác định một truy vấn, ~(1 \le p, q \le n)~

Ouput

Với mỗi truy vấn loại 2, in kết quả của đề bài trên mỗi dòng.

Simple Input 1

12
3 1 2 6 9 8 7 4 5 12 10 11
10
2 4 7
1 8 9
2 4 8
2 4 9
2 5 11
1 8 9
1 4 8
1 12 10
2 5 11
2 5 12

Simple Ouput 1

YES
YES
YES
NO
YES
YES

Sau một ngày dài làm việc mệt mỏi , Tuấn đã tắt điện thoại và đi ngủ. Nhưng lúc này, lại có một số người nhắn tin cho Tuấn.

Bạn hãy in ra thứ tự lần lượt từ đầu đến cuối tên các người nhắn tin cho Tuấn theo màn hình ứng dụng Messenger.

Input

Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~ là số lượng người nhắn tin cho Tuấn.

~n~ dòng tiếp theo chứa tên người nhắn tin cho Tuấn.

Đảm bảo tên mỗi người có độ dài không quá 10 kí tự và theo thứ tự thời gian tăng dần. Và đảm bảo rằng ứng dụng Messenger của Tuấn lúc đi ngủ hoàn toàn trống.

Output

Dòng đầu tiên in số nguyên ~m~ là số lượng người đã nhắn tin cho Tuấn.

~m~ dòng tiếp theo in ra tên người đã nhắn tin cho Tuấn theo thứ tự như màn hình ứng dụng Messenger.

Simple Input

8
AN
BINH
LY
AN
NHI
TINH
NHI
LY

Simple Output

5
LY
NHI
TINH
AN
BINH

Trong lớp học toán của thầy Lữ, có ~n~ học sinh.

Ngày hôm nay, thầy Lữ đã yêu cầu ~n~ bạn học sinh của mình mỗi người chọn một số nguyên dương lớn hơn ~0~. Được biết nếu một bạn học sinh chọn số nguyên dương ~k~ thì bạn đó sẽ yêu thích các số nguyên dương là ước của ~k~.

Ví dụ: Nam chọn số 10, thì bạn đó sẽ yêu thích các số nguyên: ~1, 2, 5, 10~.

Khi nhìn vào dãy các con số mà học sinh của mình đã chọn. Thầy Lữ đã đặt ra một câu hỏi không biết giá trị yêu thích chung lớn nhất của các nhóm bạn học sinh từ vị trí ~l~ đến vị trí ~r~ là bao nhiêu .

Giá trị yêu thích chung lớn nhất của một nhóm là số nguyên dương lớn nhất mà tất cả các bạn trong nhóm đó đều yêu thích nó.

Do là người bận rộn với công việc nên Thầy Lữ đã nhờ bạn trả lời các câu hỏi trên giúp thầy.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~ là số lượng học sinh của lớp học toán.

Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 10^9)~.

Dòng tiếp theo chứa số nguyên ~m~ ~(1 \le m \le 2 * 10^6)~ là số lượng câu hỏi của thầy Lữ,

~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l, r~ ~(1 \leq l \le r \leq n)~.

Output

Xuất ra ~m~ dòng, với mỗi dòng là câu trả lời tương ứng cho các câu hỏi của thầy Lữ.

Simple Input

5
1 2 3 4 8
3
4 5
2 5
1 2

Simple Output

4
1
1

Cho mảng ~a~ với ~n~ phần tử được đánh số từ ~1~ đến ~n~.

Điểm lớn hơn của một số tại vị trí ~i~ là số các số vị trí ~j~ mà ~a_j > a_i~ với ~i > j ~.

Cho ~m~ truy vấn ~l~, ~r~, hay cho biết tổng các điểm lớn hơn của các số trong khoảng từ ~l~ đến ~r~ này.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n, m~ ~(1 \le n, m \le 10^5)~.

Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 10^6)~.

~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l~, ~r~ ~(1 \le l \le r \le n)~.

Output

Xuất ra ~m~ dòng, với mỗi dòng là câu trả lời tương ứng.

Simple Input

5 3
5 4 1 3 2
4 5
2 5
1 2

Simple Output

5
8
1