2023_2A. An Array and Medians of Subarrays
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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, \ldots, i_k$$$ such that the following conditions are satisfied:

  • $$$1 = i_1 \lt i_2 \lt \ldots \lt 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)])$$$, where $$$a[l..r]$$$ denotes the subarray consisting of elements $$$a_l, a_{l + 1}, \ldots, 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,\ldots,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.

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 \lt n$$$;
  4. ($$$16$$$ points): $$$1 \le a_i \le 3$$$ for $$$1 \le i \le n$$$; each value occurs in $$$a$$$ no more than $$$n \over 2$$$ times;
  5. ($$$17$$$ points): $$$n \le 100$$$;
  6. ($$$18$$$ points): $$$n \le 2000$$$;
  7. ($$$20$$$ points): no additional restrictions.
Examples
Input
4
1 1 1 1
Output
Yes
Input
6
1 2 3 3 2 1
Output
Yes
Input
6
1 2 1 3 2 3
Output
No
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.