Increasing Triplet Subsequence

Given an array of integers, determine whether there exists an increasing subsequence of length at least 3. An increasing subsequence is a sequence of indices i, j, k such that i < j < k and nums[i] < nums[j] < nums[k]. The subsequence does not need to be contiguous.

Note: Although the term "non-decreasing" might imply that equal elements are allowed, in this problem we require a strictly increasing subsequence. For example, an array such as [1, 1, 1] should result in False, while [1, 2, 2, 3] has a valid subsequence (1, 2, 3) and should result in True.

You are required to read from standard input and print the result to standard output.

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.

For example:

5
1 2 3 4 5

outputFormat

Print True if there exists an increasing subsequence of length at least 3, otherwise print False.

5
1 2 3 4 5

True