Cho một dãy số $A_1, A_2, \ldots, A_N$ độ dài $N$. Viết chương trình xử lý các truy vấn sau:

• 1 i v: Thay đổi $A_i$ thành $v$ ($1 \le i \le N$, $1 \le v \le 10^9$).
• 2 i j: Đưa ra chỉ số của phần tử có giá trị nhỏ nhất trong đoạn $A_i, A_{i+1}, \ldots, A_j$. Nếu có nhiều phần tử như vậy, đưa ra phần tử có chỉ số nhỏ nhất ($1 \le i \le j \le N$, $1 \le v \le 10^9$).

Dãy được đánh chỉ số từ 1.

Dữ liệu vào

Dòng đầu tiên chứa độ dài $N$ của dãy số ($1 \le N \le 100\,000$).

Dòng thứ hai chứa $A_1, A_2, \ldots, A_N$ ($1 \le A_i \le 10^9$).

Dòng thứ ba chứa số lượng truy vấn $M$ ($1 \le M \le 100\,000$).

$M$ dòng tiếp theo, mỗi dòng mô tả một truy vấn.

Dữ liệu ra

Với mỗi truy vấn loại 2, đưa ra một câu trả lời trên một dòng theo thứ tự.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

3
4
4
3