Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k

such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Input format
First Line Contains an Integer T: no of test cases.

For each test case the first line contains an integer N: No of elements in the array.

Second line contains N space separated integers.

Output format
output either true or false

Sample Input 1
5

1 2 3 4 5

Sample Output 1
true

Explanation 1
Here A[0] < A[1] <A[2] hence true

Constraints
1 <= T <= 1000

1 <= N <= 10^5

0 <= A[i] <= |10^9|

It is guaranteed that sum of N over all test cases is less than 5*10^5.


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

string increasingTripleSubsequence(int n, vector<int> & nums) {

}


int main() {
    int t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        vector<int> nums(n);
        for (int i = 0; i < n; i++) {
            cin >> nums[i];
        }
        string ans = increasingTripleSubsequence( n, nums);
        cout << ans << endl;
    }


}