Maximum Triplet Product Queries

You are given an array of integers and a series of queries. There are two types of queries:

• Type 1: 1 i x updates the i-th element of the array to x.
• Type 2: 2 L R requires you to compute the maximum product of any three numbers from the subarray spanning indices L to R (inclusive). If the subarray contains fewer than 3 numbers, the answer is defined to be \(-1\).

When computing the maximum product, consider both the product of the three largest numbers and the product of the two smallest (which could be negative) with the largest number. That is, if the sorted subarray is \(a_1 \le a_2 \le \ldots \le a_m\), the answer is given by:

\[ \text{answer} = \max(a_{m} \cdot a_{m-1} \cdot a_{m-2},\;a_{1} \cdot a_{2} \cdot a_{m}) \]

Solve the problem by processing each query in the order given and printing the results for type 2 queries.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. An integer \(N\) representing the number of elements in the array.
2. A line with \(N\) space-separated integers representing the initial array.
3. An integer \(Q\) representing the number of queries.
4. \(Q\) lines, each containing three integers. For a query:
• If the first integer is 1, then the query is of the form 1 i x, meaning update the i-th element with the value \(x\).
• If the first integer is 2, then the query is of the form 2 L R, meaning output the maximum product of any three numbers in the subarray from index \(L\) to \(R\) (inclusive).

outputFormat

For each query of type 2, print the computed result on a new line to the standard output (stdout).

## sample

6
3 1 4 1 5 9
5
2 1 6
1 2 -3
2 1 6
1 6 2
2 1 6

180
180
60

</p>