Масив і медіани підмасивів

Назвемо медіаною масиву довжини $(2\cdot k+1)$ число, яке опиняється на позиції $(k+1)$ після сортування його елементів за неспаданням. Наприклад, медіанами масивів $[1]$, $[4,2,5]$ та $[6,5,1,2,3]$ є числа $1$, $4$ та $3$ відповідно.

Задано масив цілих чисел $a$ парної довжини $n$.

Визначте, чи можливо розділити $a$ на кілька масивів непарної довжини так, щоб усі медіани цих масивів були попарно рівні.

Формально, необхідно визначити, чи існує така послідовність цілих чисел $i_1,i_2,\dots ,i_k$, для якої виконуються наступні умови:

• $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)])$, де $a[l..r]$ позначає масив, що складається з елементів $a_l,a_{l+1},\dots ,a_r$, а $f(a)$ позначає медіану масиву $a$.

Вхідні дані

У першому рядку задано одне ціле парне число $n$ ($2\le n\le 2\cdot 10^5$) — довжина масиву.

У другому рядку задано $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9)$ — елементи масиву.

Гарантується, що $n$ — парне.

Вихідні дані

Виведіть «Yes», якщо можливо розділити $a$ на кілька масивів непарної довжини так, щоб усі медіани цих масивів були попарно рівні, і «No» у протилежному випадку.

Приклади

Примітка

У першому прикладі масив $[1,1,1,1]$ можна розділити на масиви $[1]$ та $[1,1,1]$ з медіанами рівними $1$.

У другому прикладі масив $[1,2,3,3,2,1]$ можна розділити на масиви $[1,2,3]$ та $[3,2,1]$ з медіанами рівними $2$.

У третьому прикладі масив $[1,2,1,3,2,3]$ неможливо розділити на кілька масивів непарної довжини з однаковими значеннями медіан.

Оцінювання

1. ($3$ бали): $n=2$;

2. ($14$ балів): $1\le a_i\le 2$ для $1\le i\le n$;

3. ($12$ балів): $a_i\le a_{i+1}$ для $1\le i<n$;

4. ($16$ балів): $1\le a_i\le 3$ для $1\le i\le n$; кожне значення зустрічається в $a$ не більше ніж $\frac{n}{2}$ разів;

5. ($17$ балів): $n\le 100$;

6. ($18$ балів): $n\le 2000$;

7. ($20$ балів): без додаткових обмежень.