E. Max Rectangle Area in Histogram - Easy
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$

Input

The first line contains a single integer, $$$T$$$, the number of testcases

The first line of each testcase contains an integer, $$$N$$$, the size of the array

The second line of each testcase contains $$$N$$$ integers

Output

You are required to print 4 lines of output per testcase.

The first line will contain $$$N$$$ integers, the $$$i^{th}$$$ integer corresponding to the value of $$$left\_extension[i]$$$

The second line will contain $$$N$$$ integers, the $$$i^{th}$$$ integer corresponding to the value of $$$right\_extension[i]$$$

The third line will contain $$$N$$$ integers, the $$$i^{th}$$$ integer corresponding to the value of $$$cover[i]$$$

The fourth line will contain a single integer, corresponding to the area of the largest rectangle that can be completely fit inside the histogram

Example
Input
1
7
2 1 4 5 1 3 3
Output
0 1 0 0 4 0 1 
0 5 1 0 2 1 0 
2 7 8 5 7 6 6 
8