Масив і медіани підмасивів#226
Назвемо медіаною масиву довжини (2 \cdot k + 1) число, яке опиняється на позиції (k + 1) після сортування його елементів за неспаданням. Наприклад, медіанами масивів , [4,2,5] та [6,5,1,2,3] є числа , та відповідно.
Задано масив цілих чисел парної довжини .
Визначте, чи можливо розділити на кілька масивів непарної довжини так, щоб усі медіани цих масивів були попарно рівні.
Формально, необхідно визначити, чи існує така послідовність цілих чисел i_1, i_2, \ldots, i_k, для якої виконуються наступні умови:
1 = i_1 < i_2 < \ldots < i_k = (n + 1);
(i_2 - i_1) \mod 2 = (i_3 - i_2) \mod 2 = \ldots = (i_k - i_{k - 1}) \mod 2 = 1;
f(a[i_1..(i_2-1)]) = f(a[i_2..(i_3-1)]) = \ldots = f(a[i_{k - 1}..(i_k - 1)]), де позначає масив, що складається з елементів a_l, a_{l + 1}, \ldots, a_r, а позначає медіану масиву .
У першому рядку задано одне ціле парне число (2 \le n \le 2 \cdot 10^5) — довжина масиву.
У другому рядку задано цілих чисел a_1,a_2,\ldots,a_n (1\le a_i\le 10^9) — елементи масиву.
Гарантується, що — парне.
Виведіть «Yes», якщо можливо розділити на кілька масивів непарної довжини так, щоб усі медіани цих масивів були попарно рівні, і «No» у протилежному випадку.
Приклад 1
Приклад 2
Приклад 3
У першому прикладі масив [1,1,1,1] можна розділити на масиви та [1,1,1] з медіанами рівними .
У другому прикладі масив [1,2,3,3,2,1] можна розділити на масиви [1,2,3] та [3,2,1] з медіанами рівними .
У третьому прикладі масив [1,2,1,3,2,3] неможливо розділити на кілька масивів непарної довжини з однаковими значеннями медіан.
( бали): n=2;
( балів): 1 \le a_i \le 2 для 1\le i\le n;
( балів): a_i \le a_{i+1} для 1\le i < n;
( балів): 1 \le a_i \le 3 для 1 \le i \le n; кожне значення зустрічається в не більше ніж n \over 2 разів;
( балів): n \le 100;
( балів): n \le 2000;
( балів): без додаткових обмежень.