Cherry
Contest: Codeforces Round 735 (Div. 2)
Difficulty rating: 800
Tags: greedy

You are given $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$. Find the maximum value of $$$max(a_l, a_{l + 1}, \ldots, a_r) \cdot min(a_l, a_{l + 1}, \ldots, a_r)$$$ over all pairs $$$(l, r)$$$ of integers for which $$$1 \le l < r \le n$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10\,000$$$)  — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, print a single integer  — the maximum possible value of the product from the statement.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Let $$$f(l, r) = max(a_l, a_{l + 1}, \ldots, a_r) \cdot min(a_l, a_{l + 1}, \ldots, a_r)$$$.

In the first test case,

- $$$f(1, 2) = max(a_1, a_2) \cdot min(a_1, a_2) = max(2, 4) \cdot min(2, 4) = 4 \cdot 2 = 8$$$.
- $$$f(1, 3) = max(a_1, a_2, a_3) \cdot min(a_1, a_2, a_3) = max(2, 4, 3) \cdot min(2, 4, 3) = 4 \cdot 2 = 8$$$.
- $$$f(2, 3) = max(a_2, a_3) \cdot min(a_2, a_3) = max(4, 3) \cdot min(4, 3) = 4 \cdot 3 = 12$$$.

So the maximum is $$$f(2, 3) = 12$$$.

In the second test case, the maximum is $$$f(1, 2) = f(1, 3) = f(2, 3) = 6$$$.

Example input:
4
3
2 4 3
4
3 2 3 1
2
69 69
6
719313 273225 402638 473783 804745 323328

Example output:
12
6
4761
381274500335

Editorial:
Do we really need to check all the subarrays?
Consider a subarray $$$(a_i, a_{i + 1}, \ldots, a_{j})$$$. If we add a new element $$$a_{j + 1}$$$, when will the new subarray $$$(a_i, a_{i + 1}, \ldots, a_{j}, a_{j + 1})$$$ give a better result? Pause and think.
The minimum of the new subarray can't get better(the minimum of a smaller subarray $$$\ge$$$ the minimum of a larger subarray). So only when $$$a_{j + 1}$$$ is greater than the previous maximum, then it will give a better result. But in that case, do we really need to check the whole subarray to get that result? Can we get the same or a better result from a smaller subarray? Think.
Here the maximum is $$$a_{j + 1}$$$. So if the minimum is not $$$a_i$$$, then the subarray $$$(a_{i + 1}, a_{i + 2}, \ldots, a_{j + 1})$$$ will give the same result. Otherwise, the minimum of $$$(a_{i + 1}, a_{i + 2}, \ldots, a_{j + 1})$$$ will not be smaller which implies that $$$(a_{i + 1}, a_{i + 2}, \ldots, a_{j + 1})$$$ will give a better result!
So if we add a new element, we don't have to check the whole subarray, checking $$$(a_i, a_{i + 1}, \ldots, a_{j})$$$ and $$$(a_{i + 1}, a_{i + 2}, \ldots, a_{j + 1})$$$ is enough.
What good this observation just brought to this world? Think.
Yes, we don't have to check subarrays with length $$$> 2$$$, because according to the observation, $$$(a_1, a_2, a_3)$$$ won't give a better result than $$$(a_1, a_2)$$$ and $$$(a_2, a_3)$$$. And subarrays with length $$$4$$$ won't give a better result than subarrays with length $$$3$$$ and subarrays with length $$$3$$$ won't give a better result than subarrays with length $$$2$$$. You got the idea, right?
Another thing to notice here is that the product of maximum and minimum of two integers is just the product of two integers. So the answer to the problem is the maximum of the products of adjacent elements in $$$a$$$.
Time Complexity: $$$\mathcal{O}(n)$$$