Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Permutation

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given a permutation of numbers from 1 to *n*. Determine whether there's a pair of integers *a*, *b* (1 ≤ *a*, *b* ≤ *n*; *a* ≠ *b*) such that the element (note, that it is usual division, not integer one) is between *a* and *b* in this permutation.

Input

First line consists of a single integer *n* (1 ≤ *n* ≤ 300000) — the size of permutation.

Second line contains *n* integers — the permutation itself.

Output

Print "YES", if such a pair exists, "NO" otherwise (in both cases without quotes, the answer is case insensitive).

Examples

Input

4

1 3 4 2

Output

NO

Input

5

1 5 2 4 3

Output

YES

Note

In the second example 2 is between 1 and 3. Additionally 4 is between 3 and 5.

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/23/2019 12:51:21 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|