Algorithm

A. Cherry
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given n integers a1,a2,,an�1,�2,…,��. Find the maximum value of max(al,al+1,,ar)min(al,al+1,,ar)���(��,��+1,…,��)⋅���(��,��+1,…,��) over all pairs (l,r)(�,�) of integers for which 1l<rn1≤�<�≤�.

Input

The first line contains a single integer t (1t100001≤�≤10000)  — the number of test cases.

The first line of each test case contains a single integer n (2n1052≤�≤105).

The second line of each test case contains n integers a1,a2,,an�1,�2,…,�� (1ai1061≤��≤106).

It is guaranteed that the sum of n over all test cases doesn't exceed 31053⋅105.

Output

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

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

output
Copy
12
6
4761
381274500335

Note

Let f(l,r)=max(al,al+1,,ar)min(al,al+1,,ar)�(�,�)=���(��,��+1,…,��)⋅���(��,��+1,…,��).

In the first test case,

• f(1,2)=max(a1,a2)min(a1,a2)=max(2,4)min(2,4)=42=8�(1,2)=���(�1,�2)⋅���(�1,�2)=���(2,4)⋅���(2,4)=4⋅2=8.
• f(1,3)=max(a1,a2,a3)min(a1,a2,a3)=max(2,4,3)min(2,4,3)=42=8�(1,3)=���(�1,�2,�3)⋅���(�1,�2,�3)=���(2,4,3)⋅���(2,4,3)=4⋅2=8.
• f(2,3)=max(a2,a3)min(a2,a3)=max(4,3)min(4,3)=43=12�(2,3)=���(�2,�3)⋅���(�2,�3)=���(4,3)⋅���(4,3)=4⋅3=12.

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

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

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define endl '\n'
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin>>t;
ll n;
while(t--){
cin>n;
ll a, b, c, max = -1;
cin>>a;
for(ll i = 1; i < n; i++){
cin>>b;
c = a * b;
max = (c > max) ? c : max;
a = b;
}
cout<<max<<endl;
}

}
Copy The Code &

Input

cmd
4
3
2 4 3
4
3 2 3 1
2
69 69
6
719313 273225 402638 473783 804745 323328

Output

cmd
12
6
4761
381274500335