You are given an array which is initially a permutation of $$$n$$$ elements: $$$A=[a_1, a_2, \dots, a_n]$$$.

The array can be modified using the following operation:

• Let $$$A=[a_1, a_2, \dots, a_k]$$$ be the current array. Select two indices $$$l$$$ and $$$r$$$ $$$(1 \leq l \leq r \leq k)$$$, remove the elements $$$a_l, a_{l+1}, \dots a_r$$$ from the array, and insert $$$min(a_l, a_{l+1}, \dots, a_r)$$$ in their place. In other words, the array becomes $$$A=[a_1, a_2, \dots, a_{l-1}, min(a_l, a_{l+1}, \dots, a_r), a_{r+1}, \dots a_k]$$$.

Print the number of different arrays that you can get by performing the given operation any number of times (possibly zero) modulo $$$998244353$$$.

Given an array of $$$n$$$ distinct elements, $$$L$$$ is said to be a left terminal minima for $$$R$$$ if $$$min(a[L ... R]) = a[L]$$$

For each $$$R$$$ from $$$1$$$ to $$$n$$$, print the number of indices $$$L$$$ ($$$L \lt R$$$) such that $$$L$$$ is a left terminal minima for $$$R$$$.

Given an array of $$$n$$$ distinct elements, $$$R$$$ is said to be a right terminal minima for $$$L$$$ if $$$min(a[L ... R]) = a[R]$$$

For each $$$R$$$ from $$$1$$$ to $$$n$$$, print the number of indices $$$L$$$ ($$$L \lt R$$$) such that $$$R$$$ is a right terminal minima for $$$L$$$.

You are given an array $$$[p_1, p_2, \dots, p_n]$$$, where all elements are distinct.

You can perform several (possibly zero) operations with it. In one operation, you can choose a contiguous subsegment of $$$p$$$ and remove all elements from that subsegment, except for the minimum element on that subsegment. For example, if $$$p = [3, 1, 4, 7, 5, 2, 6]$$$ and you choose the subsegment from the $$$3$$$-rd element to the $$$6$$$-th element, the resulting array is $$$[3, 1, 2, 6]$$$.

An array $$$a$$$ is called reachable if it can be obtained from $$$p$$$ using several (maybe zero) aforementioned operations. Calculate the number of reachable arrays, and print it modulo $$$998244353$$$.

You are given an array $$$A$$$ of size $$$N$$$, each integer representing the height of a vertical bar of a histogram. The width of each bar is 1.

You are required to find the area of the largest rectangle that can be completely fit inside the histogram.

Let's define $$$left\_extension[i]$$$ to be the number of consecutive bars to the left of $$$i^{th}$$$ bar that are greater than or equal to the $$$i^{th}$$$ bar. Show how to compute the $$$left\_extension$$$ array in $$$O(n \cdot n)$$$. Hint: Start from the previous element, and keep iterating towards the left until you reach a element that is strictly smaller.

Now, let's define $$$right\_extension[i]$$$ to be the number of consecutive bars to the right of the $$$i^{th}$$$ bar that are greater than or equal to the the $$$i^{th}$$$ bar. Show to compute $$$right\_extension$$$ array in $$$O(n \cdot n)$$$.

Finally, let's define $$$cover[i]$$$ to be the size of the largest rectangle which completely contains the $$$i^{th}$$$ vertical bar inside it. Show how to compute the $$$cover$$$ array in $$$O(n)$$$.

Using the $$$cover$$$ array, come up with an algorithm to find the largest rectangle in the histogram in $$$O(n)$$$.

Constraints

$$$1 \leq T \leq 10^3$$$

$$$1 \leq N \leq 10^3$$$

$$$1 \leq A[i] \leq 10^9$$$

Sum of $$$N$$$ over all testcases does not exceed $$$10^3$$$

You are given an array $$$A$$$ of size $$$N$$$, each integer representing the height of a vertical bar of a histogram. The width of each bar is 1.

You are required to find the area of the largest rectangle that can be completely fit inside the histogram.

Let's define $$$left\_extension[i]$$$ to be the number of consecutive bars to the left of $$$i^{th}$$$ bar that are greater than or equal to the $$$i^{th}$$$ bar. Show how to compute the $$$left\_extension$$$ array in $$$O(n)$$$.

Hint: Consider the array $$$[0, 6, 5, 4, 3, 2, 1]$$$. While computing the left extension of 1, we need to keep going to the left until we find a smaller element. The idea is to delete all the elements that we meet on our journey so that the next time we need to go through less number of elements. When we start at 1, we will be able to delete 2, 3, 4, 5, and 6. We claim that these deletions do not affect the answer for any elements that arrive after 1. This is because, if the incoming element is strictly greater than 1, they would never have been able to cross past 1. And if they were smaller than 1, then they have the power to go at least as far as 1 went, i.e, they would have also deleted 2, 3, 4, 5, 6. If we follow this deletion strategy, we will get a sequence which is strictly increasing, except the last element. And each consecutive element in this sequence is the boundary for the left extension.

So, use a stack of indices to maintain this order. This is known as a monotonic stack. If you want to refer to online resources for more hints, you can search for Stock Span. (The $$$left\_extension$$$ array is similar to the stock span array).

Now, let's define $$$right\_extension[i]$$$ to be the number of consecutive bars to the right of the $$$i^{th}$$$ bar that are greater than or equal to the the $$$i^{th}$$$ bar. Show to compute $$$right\_extension$$$ array in $$$O(n)$$$.

Finally, let's define $$$cover[i]$$$ to be the size of the largest rectangle which completely contains the $$$i^{th}$$$ vertical bar inside it. Show how to compute the $$$cover$$$ array in $$$O(n)$$$.

Using the $$$cover$$$ array, come up with an algorithm to find the largest rectangle in the histogram in $$$O(n)$$$.

Constraints

$$$1 \leq T \leq 10^6$$$

$$$1 \leq N \leq 10^6$$$

$$$1 \leq A[i] \leq 10^9$$$

Sum of $$$N$$$ over all testcases does not exceed $$$10^6$$$

You are given an array a consisting of n elements. The imbalance value of some subsegment of this array is the difference between the maximum and minimum element from this segment. The imbalance value of the array is the sum of imbalance values of all subsegments of this array.

For example, the imbalance value of array [1, 4, 1] is 9, because there are 6 different subsegments of this array:

• [1] (from index 1 to index 1), imbalance value is 0;
• [1, 4] (from index 1 to index 2), imbalance value is 3;
• [1, 4, 1] (from index 1 to index 3), imbalance value is 3;
• [4] (from index 2 to index 2), imbalance value is 0;
• [4, 1] (from index 2 to index 3), imbalance value is 3;
• [1] (from index 3 to index 3), imbalance value is 0;

You have to determine the imbalance value of the array a.