Finding a Strictly Increasing Triplet Subsequence

Given an array of integers, determine whether there exists a subsequence of length 3 that is strictly increasing. In other words, check if there exist indices i, j, k with i < j < k such that

a_i &lt; a_j &lt; a_k

If such a triplet exists, output 1; otherwise, output 0. This problem tests the ability to implement a greedy algorithm efficiently.

inputFormat

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

outputFormat

Output a single integer: 1 if there is a strictly increasing subsequence of length 3, otherwise 0.

## sample

5
1 2 3 4 5

1

</p>