Increasing Triplet Subsequence

Given an array of integers, determine whether there exists a triplet of indices \(i, j, k\) with \(i < j < k\) such that \(nums[i] < nums[j] < nums[k]\). If such a triplet exists, output true; otherwise, output false.

This problem requires an efficient solution with linear time complexity. You may assume that the array contains at least one element.

inputFormat

The first line contains an integer \(n\), representing the number of elements in the array. The second line contains \(n\) space-separated integers, representing the array elements.

outputFormat

Output a single line with true or false indicating whether an increasing triplet subsequence exists.

5
1 2 3 4 5

true