Increasing Triplet Subsequence

Given a sequence of integers, determine whether there exists a triplet (i.e. three indices i < j < k) such that:

\( nums[i] < nums[j] < nums[k] \)

The solution should run in linear time and use constant extra space.

For example, given the array [5, 1, 5, 2, 5, 3], the function should return True because the sequence (1, 2, 3) is an increasing triplet. If no such triplet exists (e.g. in a continuously decreasing or constant list), the output should be False.

inputFormat

The input is provided from stdin in the following format:

1. An integer n representing the number of elements in the array.
2. A line containing n space-separated integers.

outputFormat

Output a single line to stdout containing either True or False depending on whether there exists an increasing triplet subsequence in the given array.

## sample

2
1 2

False

</p>