Вчера Дима нашёл пустой массив и решил добавить в него несколько целых чисел. Он может неограниченное число раз выполнять следующую операцию:
Можно показать, что одновременно в массиве может быть не более одной такой пары.
Например, массив равен $$$[3, 6, 4]$$$. Если мы добавим слева число $$$3$$$, то сначала массив будет равен $$$[3, 3, 6, 4]$$$, затем два первых элемента заменятся на $$$6$$$, и массив станет равен $$$[6, 6, 4]$$$, а затем — $$$[12, 4]$$$.
После выполнения операции ровно $$$k$$$ раз он считает, что получил массив $$$a$$$ длины $$$n$$$, но не помнит, какие именно операции применил. Определите, существует ли последовательность из $$$k$$$ операций, в результате которой из пустого массива мог получиться данный массив $$$a$$$, или определите, что это невозможно.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — число наборов входных данных. Далее следуют описания наборов входных данных.
Первая строка описания каждого набора содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$n \le k \le 10^6$$$) — длину полученного массива и число операций.
Вторая строка содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^9, a_{i - 1} \ne a_i$$$) — элементы полученного массива.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных, если подходящей последовательности операций длины $$$k$$$ не существует, то выведите «NO». Иначе выведите «YES».
Вы можете выводить «YES» и «NO» в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).
83 32 1 43 72 1 42 152 163 10256 32 13 289768 96 13 290768 96 15 75 1 6 3 104 66 8 5 10
YES NO YES YES YES NO YES YES
| Codeforces Round 1027 (Div. 3) |
|---|
| Закончено |
