Array Queries

You are given an array A of length N, and you need to process Q queries. There are two types of queries:

1. Update Query (Type 1): Increase the i-th element of A by a given value. This query is given in the form:

   1 i v

   which means A[i] = A[i] + v (using 1-indexing).

2. Maximum Query (Type 2): Find the maximum element in the subarray from index l to r (inclusive). This query is given in the form:

   2 l r

   The answer to this query is given by:

   $$\max_{i=l}^{r} A_i$$

Process the queries in the order given. For each query of type 2, print the result on a new line. You must read input from standard input (stdin) and print the output to standard output (stdout).

inputFormat

The first line of input contains a single integer N (1 ≤ N ≤ 10^5), representing the number of elements in the array A. The second line contains N space-separated integers, the elements of the array A. The third line contains a single integer Q (1 ≤ Q ≤ 10^5), the number of queries. Each of the following Q lines contains three integers describing a query:

• If the first integer is 1, then it is an update query provided as: 1 i v (1-indexed);
• If the first integer is 2, then it is a maximum query provided as: 2 l r (1-indexed, inclusive).

outputFormat

For each query of type 2, output the maximum value in the specified subarray on a new line.## sample

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

5
5
5