О-о-о! Рэй снова потерял свой массив! Однако Омкар может помочь, потому что он думает, что нашел OmkArray массива Рэя. OmkArray массива \(a\) с элементами \(a_1, a_2, \ldots, a_{2k-1}\) — это массив \(b\) с элементами \(b_1, b_2, \ldots, b_{k}\) такой, что \(b_i\) равен медиане \(a_1, a_2, \ldots, a_{2i-1}\) для всех \(i\). Омкар нашел массив \(b\) размера \(n\) (\(1 \leq n \leq 2 \cdot 10^5\), \(-10^9 \leq b_i \leq 10^9\)). Для этого массива \(b\), Рэй хочет проверить утверждение Омкара и узнать, действительно ли \(b\) является OmkArray некоторого массива \(a\). Можете ли вы помочь Рэю?
Медиана набора чисел \(a_1, a_2, \ldots, a_{2i-1}\) — это число \(c_{i}\), где \(c_{1}, c_{2}, \ldots, c_{2i-1}\) представляют собой \(a_1, a_2, \ldots, a_{2i-1}\), отсортированные в неубывающем порядке.
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую YES, если существует массив \(a\) такой, что \(b_i\) является медианой \(a_1, a_2, \dots, a_{2i-1}\) для всех \(i\), и NO в противном случае. Регистр букв в YES и NO не имеет значения (поэтому yEs и No также будут приняты).
Примечание
Во втором наборе входных данных первого примера массив \([4]\) даст OmkArray \([4]\), так как медиана первого элемента равна \(4\).
В четвертом наборе входных данных первого примера массив \([3, 2, 5]\) даст OmkArray \([3, 3]\), так как медиана \(3\) равна \(3\), а медиана \(2, 3, 5\) равна \(3\).
В пятом наборе входных данных первого примера массив \([2, 1, 0, 3, 4, 4, 3]\) даст OmkArray \([2, 1, 2, 3]\), так как
- медиана \(2\) равна \(2\)
- медиана \(0, 1, 2\) равна \(1\)
- медиана \(0, 1, 2, 3, 4\) равна \(2\)
- и медиана \(0, 1, 2, 3, 3, 4, 4\) равна \(3\).
Во втором наборе входных данных второй выборки массив \([1, 0, 4, 3, 5, -2, -2, -2, -4, -3, -4, -1, 5]\) даст OmkArray \([1, 1, 3, 1, 0, -2, -1]\), как
- медиана \(1\) равна \(1\)
- медиана из \(0, 1, 4\) равна \(1\)
- медиана из \(0, 1, 3, 4, 5\) равна \(3\)
- медиана \(-2, -1, 0, 1, 3, 4, 5\) равна \(1\)
- медиана \(-4, -2, -2, -2, 0, 1, 3, 4, 5\) равна \(0\)
- медиана \(-4, -4, -3, -2, -2, -2, 0, 1, 3, 4, 5\) равна \(-2\)
- и медиана \(-4, -4, -3, -2, -2, -2, -1, 0, 1, 3, 4, 5, 5\) равна \(-1\)
Для всех случаев, когда ответ NO, можно доказать, что невозможно найти массив \(a\) такой, что \(b\) является Omkarray \(a\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4
6 2 1 3
1
4
5
4 -8 5 6 -7
2
3 3
4
2 1 2 3
|
NO
YES
NO
YES
YES
|
|
2
|
5
8
-8 2 -6 -5 -4 3 3 2
7
1 1 3 1 0 -2 -1
7
6 12 8 6 2 6 10
6
5 1 2 3 6 7
5
1 3 4 3 0
|
NO
YES
NO
NO
NO
|