L. YsaeSort
time limit per test
6.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This problem is similar to DrahSort. Please read the problem statement carefully to understand the differences

You are given an array of $$$N$$$ non-negative integers and a list of $$$Q$$$ operations that need to be performed on it. Each operation can be of the following 2 types:

  • $$$1$$$ $$$l$$$ $$$r$$$ $$$(1 \leq l \leq r \leq N)$$$ - sort the contiguous subsequence $$$[l, r]$$$ of the array
  • $$$2$$$ $$$l$$$ $$$r$$$ $$$(1 \leq l \leq r \leq N)$$$ - find the minimum required cost to sort the contiguous subsequence $$$[l, r]$$$ of the array

All first type operations will not contain any partially intersecting substrings. In other words, for every pair of updates $$$1$$$ $$$l1$$$ $$$r1$$$ and $$$1$$$ $$$l2$$$ $$$r2$$$, one of the following conditions will always be true:

  • $$$r1 \lt l2$$$
  • $$$r2 \lt l1$$$
  • $$$l1 \leq l2 \leq r2 \leq r1$$$
  • $$$l2 \leq l1 \leq r1 \leq r2$$$

The cost required to sort a substring, $$$[l, r]$$$ ($$$1 \leq l \leq r \leq N$$$), is defined as follows. You are only allowed to swap consecutive elements from the substring (any pair of indices $$$(i, i + 1)$$$ such that $$$l \leq i \leq r - 1$$$). The cost of swapping two consecutive elements is the product of the elements being swapped. The cost of sorting the entire substring is defined as the maximum cost among each individual swap.

Please note that the operations of the first type are persistent and will alter the structure of the array, while the operations of the second type won't perform any changes on it.

Input

The first line of input will contain one integer $$$N$$$ ($$$1\leq N \leq 5 \cdot 10^4$$$), representing the number of elements of the array.

The second line of input will contain $$$N$$$ integers ($$$0 \leq A[i] \leq 10^9$$$, $$$1\leq i \leq N$$$), the elements of the array.

The third line of input will contain one integer $$$Q$$$ ($$$1\leq Q \leq 5 \cdot 10^4$$$), representing the number of operations.

Each of the following $$$Q$$$ lines will contain one operation as described in the problem statement.

Output

For every query of the second type output the required cost to sort the substring.

Example
Input
10
10 9 8 7 6 5 4 3 2 1
11
1 1 2
2 1 2
2 1 3
2 1 10
2 9 10
1 3 4
2 1 4
2 3 4
2 2 3
1 1 4
2 1 4
Output
0
80
80
2
80
0
70
0
Note

1. After the first update the array looks as follows

9 10 8 7 6 5 4 3 2 1

2. For the second query we need to find the cost of sorting the substring $$$[1,2]$$$ which is 0, because the substring is already sorted

3. For the third query we need to find the cost of sorting the substring $$$[1,3]$$$. We need to perform 2 swaps (indices ($$$2$$$, $$$3$$$) cost $$$80$$$ and ($$$1$$$, $$$2$$$) cost 72). Hence the cost will be $$$80$$$

As previously mentioned in the statement, the array won't change after this query.

etc.