public static int[] findSortedSubsequence(int[] input){
        //smaller will hold elements smaller and on the left of a given array index i
        int[] smaller = new int[input.length];
        //bigger will hold elements greater and on the right of a given array index i
        int[] bigger = new int[input.length];
        //base cases

        int[] response = new int[3];

        smaller[0] = -1;
        bigger[input.length-1] = -1;
        int min =0;
        int max = input.length-1;

        for (int i = 1; i < input.length; i++) {

            //fill smaller subarray
            //try maintaining the minimum found so far and keep comparing the element with minimum so far
            if(input[i] <= input[min]){
                min = i;
                smaller[i] = -1;
            } else {
                smaller[i] = min;
            }

            //fill bigger subarray
            //try maintaining the max found so far
            int j  = input.length-i -1;
            if(input[j]<=input[max]){
                bigger[j] = max;
            } else {
                max = j;
                bigger[j] = -1;
            }

        }

        //now construct the response by iterating over smaller and bigger array alements
        //try to find an elemtent which has non-negative integer in both smaller and bigger array
        for(int i = 0; i< input.length; i++) {
            if(smaller[i] != -1 && bigger[i] != -1){
                response[0] = input[smaller[i]];
                response[1] = input[i];
                response[2] = input[bigger[i]];
                break;
            }
        }
        return response;

    }