Increasing Triplet Subsequence

You are given an array of n integers. Your task is to determine if there exists a triplet of indices i, j, k (with i < j < k) such that A_i < A_j < A_k. In other words, check whether the array contains an increasing subsequence of length three.

Input Format: The input consists of two lines. The first line contains an integer n representing the number of elements in the array. The second line contains n space-separated integers.

Output Format: Output a single line with the word "YES" if there exists an increasing triplet subsequence; otherwise, output "NO".

The solution should work in O(n) time with O(1) extra space. The complete condition in LaTeX is given by:

$$\text{Find indices } i, j, k \text{ such that } 1 \le i < j < k \le n \text{ and } A_i < A_j < A_k.$$

inputFormat

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

outputFormat

Output "YES" if there exists an increasing triplet subsequence; otherwise, output "NO".

5
1 2 3 4 5

YES