An Array and Medians of Subarrays

Let's call the median of an array of length $(2\cdot k+1)$ the number that appears in position $(k+1)$ after sorting its elements in non-decreasing order. For example, the medians of the arrays $[1]$, $[4,2,5]$, and $[6,5,1,2,3]$ are $1$, $4$, and $3$, respectively.

You are given an array of integers $a$ of even length $n$.

Determine whether it is possible to split $a$ into several subarrays of odd length such that all the medians of these subarrays are pairwise equal.

Formally, you need to determine whether there exists a sequence of integers $i_1,i_2,\dots ,i_k$ such that the following conditions are satisfied:

• $1=i_1<i_2<\dots <i_k=(n+1)$;

• $(i_2-i_1)\mathrm{mod}2=(i_3-i_2)\mathrm{mod}2=\dots =(i_k-i_{k-1})\mathrm{mod}2=1$;

• $f(a[i_1..(i_2-1)])=f(a[i_2..(i_3-1)])=\dots =f(a[i_{k-1}..(i_k-1)])$, where $a[l..r]$ denotes the subarray consisting of elements $a_l,a_{l+1},\dots ,a_r$, and $f(a)$ denotes the median of the array $a$.

Input

The first line contains a single even integer $n$ ($2\le n\le 2\cdot 10^5$) — the length of the array.

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9)$ — the elements of the array.

It is guaranteed that $n$ is even.

Output

Output "Yes" if it is possible to divide $a$ into several subarrays of odd length in such a way that all medians of these subarrays are pairwise equal, and "No" otherwise.

Examples

Note

In the first example, the array $[1,1,1,1]$ can be divided into the arrays $[1]$ and $[1,1,1]$ with medians equal to $1$.

In the second example, the array $[1,2,3,3,2,1]$ can be divided into the arrays $[1,2,3]$ and $[3,2,1]$ with medians equal to $2$.

In the third example, the array $[1,2,1,3,2,3]$ cannot be divided into several arrays of odd length with the same median values.

Scoring

1. ($3$ points): $n=2$;

2. ($14$ points): $1\le a_i\le 2$ for $1\le i\le n$;

3. ($12$ points): $a_i\le a_{i+1}$ for $1\le i<n$;

4. ($16$ points): $1\le a_i\le 3$ for $1\le i\le n$; each value occurs in $a$ no more than $\frac{n}{2}$ times;

5. ($17$ points): $n\le 100$;

6. ($18$ points): $n\le 2000$;

7. ($20$ points): no additional restrictions.