Майк получил в подарок на день рождения массив \(a\) длины \(n\) и решил протестировать, насколько он красивый.
Массив пройдет \(i\)-й тест на красоту, если существует способ из изначального массива путем некоторого (возможно, нулевого) количества операций разреза получить массив с суммой элементов, равной \(s_i\).
Операция разреза массива происходит следующим образом:
- Вычисляется \(mid = \lfloor\frac{max(array) + min(array)}{2}\rfloor\), где \(max\) и \(min\) — это функции нахождения максимального и минимального элемента массива. Иными словами, \(mid\) равно сумме максимального и минимального элементов \(array\), деленной на \(2\) с округлением вниз.
- Далее массив разделяется на две части \(\mathit{left}\) и \(right\). В \(\mathit{left}\) попадают все элементы массива, которые имеют значение меньшее либо равное \(mid\), а в массив \(right\) попадают все элементы, которые больше \(mid\). Элементы в \(\mathit{left}\) и \(right\) сохраняют свой относительный порядок, который был в \(array\).
- Третьим шагом выбирается, какой из массивов \(\mathit{left}\) или \(right\) мы хотим оставить. Выбранный массив заменит собой текущий, а другой навсегда удалится.
Вам требуется помочь Майку определить результаты \(q\) тестов на красоту.
Заметьте, что вы тестируете красоту массива \(a\), поэтому вы начинаете каждый тест на красоту с изначальным (заданным) массивом \(a\). Таким образом, первый разрез (если он необходим) всегда совершается над массивом \(a\).
Выходные данные
Для каждого набора входных данных выведите \(q\) строк, каждая из которых должна содержать «Yes», если соответствующий тест на красоту пройден, и «No» в противном случае.
Примечание
Объяснение первого набора входных данных:
- Получить массив с суммой \(s_1 = 1\) мы можем следующим способом:
1.1 \(a = [1, 2, 3, 4, 5]\), \(mid = \frac{1+5}{2} = 3\), \(\mathit{left} = [1, 2, 3]\), \(right = [4, 5]\). Мы выбираем оставить массив \(\mathit{left}\).
1.2 \(a = [1, 2, 3]\), \(mid = \frac{1+3}{2} = 2\), \(\mathit{left} = [1, 2]\), \(right = [3]\). Мы выбираем оставить массив \(\mathit{left}\).
1.3 \(a = [1, 2]\), \(mid = \frac{1+2}{2} = 1\), \(\mathit{left} = [1]\), \(right = [2]\). Мы выбираем оставить массив \(\mathit{left}\) с суммой, равной \(1\).
- Массив с суммой \(s_2 = 8\) можно показать, что получить невозможно.
- Получить массив с суммой \(s_3 = 9\) мы можем следующим способом:
3.1 \(a = [1, 2, 3, 4, 5]\), \(mid = \frac{1+5}{2} = 3\), \(\mathit{left} = [1, 2, 3]\), \(right = [4, 5]\). Мы выбираем оставить массив \(right\) с суммой, равной \(9\).
- Массив с суммой \(s_4 = 12\) можно показать, что получить невозможно.
- Получить массив с суммой \(s_5 = 6\) мы можем следующим способом:
5.1 \(a = [1, 2, 3, 4, 5]\), \(mid = \frac{1+5}{2} = 3\), \(\mathit{left} = [1, 2, 3]\), \(right = [4, 5]\). Мы выбираем оставить массив \(\mathit{left}\) с суммой, равной \(6\).
Объяснение второго набора входных данных:
- Массив с суммой \(s_1 = 1\) можно показать, что получить невозможно.
- Получить массив с суммой \(s_2 = 2\) мы можем следующим способом:
2.1 \(a = [3, 1, 3, 1, 3]\), \(mid = \frac{1+3}{2} = 2\), \(\mathit{left} = [1, 1]\), \(right = [3, 3, 3]\). Мы выбираем оставить массив \(\mathit{left}\) с суммой \(2\).
- Массив с суммой \(s_3 = 3\) можно показать, что получить невозможно.
- Получить массив с суммой \(s_4 = 9\) мы можем следующим способом:
4.1 \(a = [3, 1, 3, 1, 3]\), \(mid = \frac{1+3}{2} = 2\), \(\mathit{left} = [1, 1]\), \(right = [3, 3, 3]\). Мы выбираем оставить массив \(right\) с суммой \(9\).
- Мы можем получить \(s_5 = 11\) без операций разреза, потому что изначальная сумма уже была равна \(11\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5 5
1 2 3 4 5
1
8
9
12
6
5 5
3 1 3 1 3
1
2
3
9
11
|
Yes
No
Yes
No
Yes
No
Yes
No
Yes
Yes
|