Это сложная версия задачи. Единственное отличие состоит в том, что в этой версии каждый должен дать конфеты не более чем одному человеку и получить конфеты не более чем от одного человека. Обратите внимание, что посылка не может пройти обе версии задачи одновременно. Вы можете делать взломы, только если обе версии задачи решены.
После экзамена Daniel и его друзья собираются устроить вечеринку. Все придут с конфетами.
На вечеринке будут присутствовать \(n\) человек. Изначально у \(i\)-го человека есть \(a_i\) конфет. Во время вечеринки они будут обмениваться конфетами. Для этого они выстроятся в произвольном порядке и каждый из них сделает следующее не более одного раза:
- Выберет целое число \(p\) (\(1 \le p \le n\)) и неотрицательное целое число \(x\), затем даст \(2^{x}\) конфет \(p\)-му человеку. Заметим, что человек не может отдать больше конфет, чем у него есть в данный момент (он мог получить конфеты от кого-то другого), и он не может отдать конфеты самому себе.
Daniel любит справедливость, поэтому он будет счастлив тогда и только тогда, когда каждый получит конфеты от не более чем одного человека. В то же время его друг Tom любит среднее, поэтому он будет счастлив тогда и только тогда, когда у всех людей будет одинаковое количество конфет после всех обменов.
Определите, существует ли способ обменяться конфетами так, чтобы Daniel и Tom были счастливы после обменов.
Выходные данные
Для каждого набора входных данных выведите «Yes» (без кавычек), если существует способ обменяться конфетами так, чтобы Daniel и Tom были счастливы, и выведите «No» (без кавычек) в противном случае.
Вы можете вывести ответ в любом регистре (верхнем или нижнем). Например, строки «yEs», «yes», «Yes», и «YES» будут распознаны как положительный ответ.
Примечание
В первом наборе входных данных второй человек даёт \(1\) конфету первому человеку, поэтому у всех людей есть по \(3\) конфеты.
Во втором наборе входных данных четвёртый человек даёт \(1\) конфету второму человеку, пятый человек даёт \(2\) конфеты первому человеку, третий человек ничего не делает. После всех обменов у каждого есть по \(3\) конфеты.
В третьем наборе входных данных невозможно сделать так, чтобы у всех людей было одинаковое количество конфет.
В четвёртом наборе входных данных двум людям не нужно ничего делать.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3
2 4 3
5
1 2 3 4 5
6
1 4 7 1 5 4
2
20092043 20092043
12
9 9 8 2 4 4 3 5 1 1 1 1
6
2 12 7 16 11 12
|
Yes
Yes
No
Yes
No
Yes
|