I. In the Team Photo
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The contest ends with a long photo session. The $$$n$$$ participants sit in a single row, and each of them wears the jersey of the university they competed for years ago. Participant $$$i$$$ wears the jersey $$$a_i$$$, so the row is described by $$$a_1,a_2,\ldots,a_n$$$.

The archivist writes a caption for every group of consecutive participants that the photographer shoots. Two people from the same university look the same on the photo and cannot be separated in the caption, but a participant who is the only one wearing their jersey inside the group can always be named. Such a participant is a unique witness of that group.

Formally, take any non-empty contiguous stretch of seats $$$a_l,a_{l+1},\ldots,a_r$$$, and count jerseys using only the positions from $$$l$$$ through $$$r$$$. The stretch has a unique witness if there is at least one position $$$i$$$, $$$l \le i \le r$$$, such that the jersey $$$a_i$$$ occurs exactly once inside that stretch.

Only one such position is needed. The jersey does not have to be unique in the whole row: if it also appears in other parts of the row, it is still a witness where it appears alone inside the stretch.

Determine whether every non-empty contiguous stretch has a unique witness.

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of participants.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^6 \le a_i \le 10^6$$$) — the jerseys worn by the participants.

The input contains exactly one instance.

Output

Print YES if every non-empty contiguous stretch contains at least one jersey whose frequency inside that stretch is exactly $$$1$$$. Otherwise, print NO.

The answer is compared as a case-sensitive token.

Examples
Input
5
1 2 1 3 2
Output
YES
Input
2
7 7
Output
NO
Input
3
1 2 2
Output
NO
Note

In the first example, the jersey $$$3$$$ witnesses the whole row. Jerseys $$$1$$$ and $$$2$$$ repeat along the row, but this does not prevent the answer from being YES.

In the second example, the stretch consisting of both seats contains the jersey $$$7$$$ twice and has no unique witness.

In the third example, the whole row has the witness $$$1$$$, but the stretch $$$[2,2]$$$ formed by the last two seats has no unique witness. Therefore checking only the complete row is not sufficient.