description: You are given n integers a_1, a_2, …, a_n. Find the maximum value of max(a_l, a_{l + 1}, …, a_r) ⋅ min(a_l, a_{l + 1}, …, a_r) over all pairs (l, r) of integers for which 1 ≤ l < r ≤ n.
  
  Input
  
  The first line contains a single integer t (1 ≤ t ≤ 10 000) — the number of test cases.
  
  The first line of each test case contains a single integer n (2 ≤ n ≤ 10^5).
  
  The second line of each test case contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^6).
  
  It is guaranteed that the sum of n over all test cases doesn't exceed 3 ⋅ 10^5.
  
  Output
  
  For each test case, print a single integer — the maximum possible value of the product from the statement.
  
  Example
  
  Input
  
  
  4
  3
  2 4 3
  4
  3 2 3 1
  2
  69 69
  6
  719313 273225 402638 473783 804745 323328
  
  
  Output
  
  
  12
  6
  4761
  381274500335
  
  Note
  
  Let f(l, r) = max(a_l, a_{l + 1}, …, a_r) ⋅ min(a_l, a_{l + 1}, …, a_r).
  
  In the first test case, 
  
    * f(1, 2) = max(a_1, a_2) ⋅ min(a_1, a_2) = max(2, 4) ⋅ min(2, 4) = 4 ⋅ 2 = 8. 
    * f(1, 3) = max(a_1, a_2, a_3) ⋅ min(a_1, a_2, a_3) = max(2, 4, 3) ⋅ min(2, 4, 3) = 4 ⋅ 2 = 8. 
    * f(2, 3) = max(a_2, a_3) ⋅ min(a_2, a_3) = max(4, 3) ⋅ min(4, 3) = 4 ⋅ 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.
solution: #include <bits/stdc++.h>
  using namespace std;
  const int mod = 1000000007;
  vector<long long> nextGreaterToLeft(vector<long long> arr, long long n) {
    stack<long long> s;
    vector<long long> ans;
    for (int i = 0; i < n; i++) {
      if (s.empty())
        ans.push_back(-1);
      else {
        while (s.size() > 0 and arr[s.top()] < arr[i]) s.pop();
        if (s.empty())
          ans.push_back(-1);
        else
          ans.push_back(s.top());
      }
      s.push(i);
    }
    return ans;
  }
  vector<long long> nextSmallerToRight(vector<long long> arr, long long n) {
    stack<long long> s;
    vector<long long> ans;
    for (long long i = n - 1; i >= 0; i--) {
      if (s.empty())
        ans.push_back(-1);
      else {
        while (s.size() > 0 and arr[s.top()] > arr[i]) s.pop();
        if (s.empty())
          ans.push_back(-1);
        else
          ans.push_back(s.top());
      }
      s.push(i);
    }
    reverse(ans.begin(), ans.end());
    return ans;
  }
  vector<long long> nextSmallerToLeft(vector<long long> arr, int n) {
    stack<long long> s;
    vector<long long> ans;
    for (int i = 0; i < n; i++) {
      if (s.empty())
        ans.push_back(-1);
      else {
        while (s.size() > 0 and arr[s.top()] > arr[i]) s.pop();
        if (s.empty())
          ans.push_back(-1);
        else
          ans.push_back(s.top());
      }
      s.push(i);
    }
    return ans;
  }
  vector<long long> nextGreaterToRight(vector<long long> arr, long long n) {
    stack<long long> s;
    vector<long long> ans;
    for (int i = n - 1; i >= 0; i--) {
      if (s.empty())
        ans.push_back(-1);
      else {
        while (s.size() > 0 and arr[s.top()] < arr[i]) s.pop();
        if (s.empty())
          ans.push_back(-1);
        else
          ans.push_back(s.top());
      }
      s.push(i);
    }
    reverse(ans.begin(), ans.end());
    return ans;
  }
  int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    long long T = 1;
    cin >> T;
    while (T--) {
      vector<long long> v;
      long long n;
      cin >> n;
      for (int i = 0; i < n; i++) {
        long long val;
        cin >> val;
        v.push_back(val);
      }
      vector<long long> Gleft = nextGreaterToLeft(v, n);
      vector<long long> Gright = nextGreaterToRight(v, n);
      vector<long long> Sleft = nextSmallerToLeft(v, n);
      vector<long long> Sright = nextSmallerToRight(v, n);
      long long maxi = (long long)1e-18;
      for (int i = 0; i < n; i++) {
        long long left = -1, right = -1;
        if (Gleft[i] != -1 and Sleft[i] != -1) {
          left = max(Gleft[i], Sleft[i]);
        } else if (Gleft[i] != -1) {
          left = Gleft[i];
        } else if (Sleft[i] != -1) {
          left = Sleft[i];
        }
        left = (left == -1 ? 0 : v[left]);
        if (Gright[i] != -1 and Sright[i] != -1) {
          right = min(Gright[i], Sright[i]);
        } else if (Gright[i] != -1) {
          right = Gright[i];
        } else if (Sright[i] != -1) {
          right = Sright[i];
        }
        right = (right == -1 ? 0 : v[right]);
        maxi = max(maxi, v[i] * max(left, right));
      }
      cout << maxi << endl;
    }
    return 0;
  }
  