Stock Price Queries

You are given the stock prices for n days and a series of queries. There are two types of queries:

• Update Query: 1 d p — Update the price on the d-th day to p.
• Range Maximum Query: 2 l r — Query the maximum stock price between days l and r (inclusive).

Internally, you'll need to maintain a data structure to efficiently update a day’s price and to respond to maximum queries over an interval.

Formally, let \( A = [a_1, a_2, \dots, a_n] \) be the array of stock prices. For an update query of the form 1 d p, you must set \( a_d = p \). For a range maximum query \(2\ l\ r\), output \[ \max_{l \le i \le r} a_i \]

The input is given via standard input, and the answers for all range maximum queries should be printed to standard output (one per line).

inputFormat

The input is given via stdin in the following format:

n
p1 p2 ... pn
q
query1
query2
...
queryq

Here:

• n is the number of days.
• The second line contains n space-separated integers representing the initial stock prices.
• q is the number of queries.
• Each query is given on a new line and is either in the format 1 d p for an update or 2 l r for a range maximum query.

outputFormat

For each query of type 2 l r, output the maximum stock price in the given range on a new line in standard output (stdout).

## sample

5
10 20 30 40 50
6
2 1 5
1 3 25
2 1 5
2 2 4
1 5 10
2 1 5

50
50
40
40

</p>