Non-Subsequence Partition

You are given a sequence of integers (a_1, a_2, \dots, a_n). The task is to split the sequence into two non-empty contiguous segments at some index (l) (i.e. the segments are (a_1, a_2, \dots, a_l) and (a_{l+1}, a_{l+2}, \dots, a_n), where (1 \le l < n)).

The catch is that you should choose the index (l) such that neither segment is a subsequence of the other. In other words, it must hold that: [ \text{Segment 1} \not\subseteq \text{Segment 2} \quad \text{and} \quad \text{Segment 2} \not\subseteq \text{Segment 1} ]

Recall that a sequence (s) is a subsequence of another sequence (t) if (s) can be obtained by deleting zero or more elements from (t) without changing the order of the remaining elements.

Determine whether there is a valid way to split the sequence. If such a partition exists, print "YES"; otherwise, print "NO".

inputFormat

The first line contains a single integer \(n\) (\(2 \leq n \leq 10^5\)), the number of elements in the sequence.

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\), representing the sequence.

outputFormat

Output a single line containing either "YES" if there exists a valid partition, or "NO" otherwise.

sample

2
1 2

YES