#include <iostream>
#include <vector>
using namespace std;

//Find a sorted subsequence of size 3 in linear time
class Solution
{
private:
	int	seq1;
	int seq2[2];

public:
	vector<int>	find3IncreasingNumbers(int * arr, int n)
	{
		vector<int>	result;
		if(n < 3)	return result;
		
		bool seq2Filled = false;
		seq1 = arr[0];
		
		for(int i = 1; i < n; ++i)
		{
			if(arr[i] < seq1)
				seq1 = arr[i];
			else if(arr[i] == seq1)
				continue;
			else if(!seq2Filled || arr[i] <= seq2[1]) {
				seq2[0] = seq1;
				seq2[1] = arr[i];
				seq2Filled = true;
			}
			else {
				result.push_back(seq2[0]);
				result.push_back(seq2[1]);
				result.push_back(arr[i]);
				break;
			}
		}
		
		return result;
	}
};

int main() {
	int arr1[] = {12, 11, 10, 5, 6, 2, 30};
	int arr2[] = {1, 2, 3, 4};
	int arr3[] = {4, 3, 1, 2};
	int arr4[] = {12, 11, 10, 5, 6, 2, 30};
	Solution so;
	vector<int>	resultTriple;
	
	resultTriple = so.find3IncreasingNumbers(arr1, sizeof(arr1)/sizeof(int));
	if(resultTriple.size())
		cout<<"Result of arr1 : " <<resultTriple[0]<<" "<<resultTriple[1]<<" "<<resultTriple[2]<<endl;
	else
		cout << "Did not find increasing triple in arr1."<<endl;
	
	resultTriple = so.find3IncreasingNumbers(arr2, sizeof(arr2)/sizeof(int));
	if(resultTriple.size())
		cout<<"Result of arr2 : " <<resultTriple[0]<<" "<<resultTriple[1]<<" "<<resultTriple[2]<<endl;
	else
		cout << "Did not find increasing triple in arr2."<<endl;
		
	resultTriple = so.find3IncreasingNumbers(arr3, sizeof(arr3)/sizeof(int));
	if(resultTriple.size())
		cout<<"Result of arr3 : " <<resultTriple[0]<<" "<<resultTriple[1]<<" "<<resultTriple[2]<<endl;
	else
		cout << "Did not find increasing triple in arr3."<<endl;
		
	resultTriple = so.find3IncreasingNumbers(arr4, sizeof(arr4)/sizeof(int));
	if(resultTriple.size())
		cout<<"Result of arr4 : " <<resultTriple[0]<<" "<<resultTriple[1]<<" "<<resultTriple[2]<<endl;
	else
		cout << "Did not find increasing triple in arr4."<<endl;
	
	
	return 0;
}