Program 1

/*
Given an array A of N integers, Your task is to complete the function find3Numbers which finds any 3 elements in it such that A[i] < A[j] < A[k] and i < j < k. You need to return them as a vector, if no such element is present then return the empty vector of size 0.

Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains an integer N denoting the size of the array A in the next line are N space separated values of the array A.

Output:
For each test case in a new line output will be 1 if the sub-sequence returned by the function is present in array A else 0.

Constraints:
1 <= T <= 100
1 <= N <= 105
1 <= A[ ] <= 106

Example:
Input:
2
5
1 2 1 1 3
3
1 1 3
Output:
1
0

Explanation:
There are 2 test cases
For first test case
a sub-sequence 1 2 3 exist 
For second test case
no such sub-sequence exist
/*


{
import java.util.*;
class SubSeq{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		while(t-->0){int i=0;
			int n=sc.nextInt();
			int[] a=new int[1000];
			while(i<n){
				a[i]=sc.nextInt();
				i++;
			}
			GfG g=new GfG();
			ArrayList aa = g.find3Numbers(a,n);
			if(aa.size()==3)
			{int x=(int)aa.get(0);
			int y=(int)aa.get(1);
			int z=(int)aa.get(2);
			if(x<y && y<z)
				System.out.println("1");
			elsejh
			System.out.println("0");
			}
			else{
				System.out.println("0");
			}
		}
	}
}
}

/*Please note that it's Function problem i.e.
you need to write your solution in the form of Function(s) only.
Driver Code to call/invoke your function is mentioned above.*/

/*Complete the function below*/
class GfG{
	public static ArrayList find3Numbers(int[] a,int n){
	    int[] inc=new int[n];
	    int[] dec=new int[n];
	    int max=n-1,min=0;
	    inc[0]=-1;
	    dec[n-1]=-1;
	    for(int i=1;i<n;i++)
	{
	    if(a[i]>a[min])
	    {
	        inc[i]=min;
	    }
	    else
	    {
	        inc[i]=-1;
	        min=i;
	    }
	}
	for(int j=n-2;j>0;j--)
	{
	    if(a[j]<a[max])
	    {
	        dec[j]=max;
	    }
	    else
	    {
	        dec[j]=-1;
	        max=j;
	    }
	}
	ArrayList v=new ArrayList();
	for(int i=0;i<n;i++)
	{
	    if(dec[i]!=-1 && inc[i]!=-1)
	    {
	     v.add(a[inc[i]]);
	     v.add(a[i]);
	     v.add(a[dec[i]]);
	     break;
	    }
	}
     return v;      //add code here.
    }
}