// Forked from http://i...content-available-to-author-only...e.com/QefD9V // I don't think ideone tracks this
// Originally by Kenneth: http://w...content-available-to-author-only...s.org/find-a-sorted-subsequence-of-size-3-in-linear-time/#comment-1573367479
// Original had this great algorithm, but a clumsy and weird implementation (esp. the code outside the loop itself)
 
#include <iostream>
#include <vector>
 
using namespace std;
 
//Find a sorted subsequence of size 3 in one pass, linear time
//returns an empty list on not-found
vector<int>	find3IncreasingNumbers(int * arr, int n)
{
	int min_so_far = arr[0];
	int c_low, c_mid; // candidates
	bool have_candidates = false;
 
	for(int i = 1; i < n; ++i) 	{
		if(arr[i] <= min_so_far)  // less-or-equal prevents values == min from ending up as mid candidates, without a separate else if() continue;
			min_so_far = arr[i];
		else if(!have_candidates || arr[i] <= c_mid) {
			// If any sequence exists with a middle-numbers we've already seen (and that we haven't already finished)
			// then one exists involving these candidates
			c_low = min_so_far;
			c_mid = arr[i];
			have_candidates = true;
		} else {
			// have candidates and arr[i] > c_mid
			return vector<int> ( { c_low, c_mid, arr[i] } );
		}
	}
 
	return vector<int>();  // not-found
}
 
int main()
{
    int array_num = 1;
 
// http://stackoverflow.com/questions/20913103/is-it-possible-to-pass-a-brace-enclosed-initializer-as-a-macro-parameter
#define TRYFIND(...) do { \
    	int arr[] = __VA_ARGS__ ; \
    	vector<int> resultTriple = find3IncreasingNumbers(arr, sizeof(arr)/sizeof(arr[0])); \
		if(resultTriple.size()) \
			cout<<"Result of arr" << array_num << ": " <<resultTriple[0]<<" "<<resultTriple[1]<<" "<<resultTriple[2]<<endl; \
		else \
			cout << "Did not find increasing triple in arr" << array_num << "." <<endl; \
		array_num++; \
    }while(0)
 
    TRYFIND( {12, 11, 10, 5, 6, 2, 30} );
	TRYFIND( {1, 2, 3, 4} );
	TRYFIND( {4, 3, 1, 2} );
	TRYFIND( {12, 1, 11, 10, 5, 4, 3} );
	TRYFIND( {12, 1, 11, 10, 5, 4, 7} );
	TRYFIND( {12, 11, 10, 5, 2, 4, 1, 3} );
	TRYFIND( {12, 11, 10, 5, 2, 4, 1, 6} );
    TRYFIND( {5,13,6,10,3,7,2} );
    TRYFIND( {1, 5, 1, 5, 2, 2, 5} );
    TRYFIND( {1, 5, 1, 5, 2, 1, 5} );
    TRYFIND( {2, 3, 1, 4} );
    TRYFIND( {3, 1, 2, 4} );
    TRYFIND( {2, 4} );
 
	return 0;
}

Ly8gRm9ya2VkIGZyb20gaHR0cDovL2kuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmUuY29tL1FlZkQ5ViAvLyBJIGRvbid0IHRoaW5rIGlkZW9uZSB0cmFja3MgdGhpcwovLyBPcmlnaW5hbGx5IGJ5IEtlbm5ldGg6IGh0dHA6Ly93Li4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5zLm9yZy9maW5kLWEtc29ydGVkLXN1YnNlcXVlbmNlLW9mLXNpemUtMy1pbi1saW5lYXItdGltZS8jY29tbWVudC0xNTczMzY3NDc5Ci8vIE9yaWdpbmFsIGhhZCB0aGlzIGdyZWF0IGFsZ29yaXRobSwgYnV0IGEgY2x1bXN5IGFuZCB3ZWlyZCBpbXBsZW1lbnRhdGlvbiAoZXNwLiB0aGUgY29kZSBvdXRzaWRlIHRoZSBsb29wIGl0c2VsZikKCiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHZlY3Rvcj4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgovL0ZpbmQgYSBzb3J0ZWQgc3Vic2VxdWVuY2Ugb2Ygc2l6ZSAzIGluIG9uZSBwYXNzLCBsaW5lYXIgdGltZQovL3JldHVybnMgYW4gZW1wdHkgbGlzdCBvbiBub3QtZm91bmQKdmVjdG9yPGludD4JZmluZDNJbmNyZWFzaW5nTnVtYmVycyhpbnQgKiBhcnIsIGludCBuKQp7CglpbnQgbWluX3NvX2ZhciA9IGFyclswXTsKCWludCBjX2xvdywgY19taWQ7IC8vIGNhbmRpZGF0ZXMKCWJvb2wgaGF2ZV9jYW5kaWRhdGVzID0gZmFsc2U7CgoJZm9yKGludCBpID0gMTsgaSA8IG47ICsraSkgCXsKCQlpZihhcnJbaV0gPD0gbWluX3NvX2ZhcikgIC8vIGxlc3Mtb3ItZXF1YWwgcHJldmVudHMgdmFsdWVzID09IG1pbiBmcm9tIGVuZGluZyB1cCBhcyBtaWQgY2FuZGlkYXRlcywgd2l0aG91dCBhIHNlcGFyYXRlIGVsc2UgaWYoKSBjb250aW51ZTsKCQkJbWluX3NvX2ZhciA9IGFycltpXTsKCQllbHNlIGlmKCFoYXZlX2NhbmRpZGF0ZXMgfHwgYXJyW2ldIDw9IGNfbWlkKSB7CgkJCS8vIElmIGFueSBzZXF1ZW5jZSBleGlzdHMgd2l0aCBhIG1pZGRsZS1udW1iZXJzIHdlJ3ZlIGFscmVhZHkgc2VlbiAoYW5kIHRoYXQgd2UgaGF2ZW4ndCBhbHJlYWR5IGZpbmlzaGVkKQoJCQkvLyB0aGVuIG9uZSBleGlzdHMgaW52b2x2aW5nIHRoZXNlIGNhbmRpZGF0ZXMKCQkJY19sb3cgPSBtaW5fc29fZmFyOwoJCQljX21pZCA9IGFycltpXTsKCQkJaGF2ZV9jYW5kaWRhdGVzID0gdHJ1ZTsKCQl9IGVsc2UgewoJCQkvLyBoYXZlIGNhbmRpZGF0ZXMgYW5kIGFycltpXSA+IGNfbWlkCgkJCXJldHVybiB2ZWN0b3I8aW50PiAoIHsgY19sb3csIGNfbWlkLCBhcnJbaV0gfSApOwoJCX0KCX0KCglyZXR1cm4gdmVjdG9yPGludD4oKTsgIC8vIG5vdC1mb3VuZAp9CgppbnQgbWFpbigpCnsKICAgIGludCBhcnJheV9udW0gPSAxOwoKLy8gaHR0cDovL3N0YWNrb3ZlcmZsb3cuY29tL3F1ZXN0aW9ucy8yMDkxMzEwMy9pcy1pdC1wb3NzaWJsZS10by1wYXNzLWEtYnJhY2UtZW5jbG9zZWQtaW5pdGlhbGl6ZXItYXMtYS1tYWNyby1wYXJhbWV0ZXIKI2RlZmluZSBUUllGSU5EKC4uLikgZG8geyBcCiAgICAJaW50IGFycltdID0gX19WQV9BUkdTX18gOyBcCiAgICAJdmVjdG9yPGludD4gcmVzdWx0VHJpcGxlID0gZmluZDNJbmNyZWFzaW5nTnVtYmVycyhhcnIsIHNpemVvZihhcnIpL3NpemVvZihhcnJbMF0pKTsgXAoJCWlmKHJlc3VsdFRyaXBsZS5zaXplKCkpIFwKCQkJY291dDw8IlJlc3VsdCBvZiBhcnIiIDw8IGFycmF5X251bSA8PCAiOiAiIDw8cmVzdWx0VHJpcGxlWzBdPDwiICI8PHJlc3VsdFRyaXBsZVsxXTw8IiAiPDxyZXN1bHRUcmlwbGVbMl08PGVuZGw7IFwKCQllbHNlIFwKCQkJY291dCA8PCAiRGlkIG5vdCBmaW5kIGluY3JlYXNpbmcgdHJpcGxlIGluIGFyciIgPDwgYXJyYXlfbnVtIDw8ICIuIiA8PGVuZGw7IFwKCQlhcnJheV9udW0rKzsgXAogICAgfXdoaWxlKDApCgogICAgVFJZRklORCggezEyLCAxMSwgMTAsIDUsIDYsIDIsIDMwfSApOwoJVFJZRklORCggezEsIDIsIDMsIDR9ICk7CglUUllGSU5EKCB7NCwgMywgMSwgMn0gKTsKCVRSWUZJTkQoIHsxMiwgMSwgMTEsIDEwLCA1LCA0LCAzfSApOwoJVFJZRklORCggezEyLCAxLCAxMSwgMTAsIDUsIDQsIDd9ICk7CglUUllGSU5EKCB7MTIsIDExLCAxMCwgNSwgMiwgNCwgMSwgM30gKTsKCVRSWUZJTkQoIHsxMiwgMTEsIDEwLCA1LCAyLCA0LCAxLCA2fSApOwogICAgVFJZRklORCggezUsMTMsNiwxMCwzLDcsMn0gKTsKICAgIFRSWUZJTkQoIHsxLCA1LCAxLCA1LCAyLCAyLCA1fSApOwogICAgVFJZRklORCggezEsIDUsIDEsIDUsIDIsIDEsIDV9ICk7CiAgICBUUllGSU5EKCB7MiwgMywgMSwgNH0gKTsKICAgIFRSWUZJTkQoIHszLCAxLCAyLCA0fSApOwogICAgVFJZRklORCggezIsIDR9ICk7CgoJcmV0dXJuIDA7Cn0=