Sequence and Queries 16

You are given a sequence $A_1, A_2, \ldots, A_N$ of length $N$. Write a program that processes the following two kinds of queries.

• 1 i v: Replace $A_i$ with $v$. ($1 \le i \le N$, $1 \le v \le 10^9$)
• 2 i j: Print the index of the smallest value among $A_i, A_{i+1}, \ldots, A_j$. If several elements share that smallest value, print the smallest index among them. ($1 \le i \le j \le N$)

Indices of the sequence start at 1.

The first line contains the length of the sequence $N$. ($1 \le N \le 100{,}000$)

The second line contains $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 10^9$)

The third line contains the number of queries $M$. ($1 \le M \le 100{,}000$)

Each of the next $M$ lines contains one query.

For each query of type 2, print its answer on its own line, in the order the queries are given.