H. Олимпийский тимбилдинг
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Гвозден и Вукашин участвует в шахматной олимпиаде и хочет устроить тимбилдинг. Он собрал $$$n$$$ игроков, где $$$n$$$ является степенью $$$2$$$, и предложил заняться спортом. Гвозден и Вукашин входит в число этих $$$n$$$ человек.

Одно из спортивных мероприятий — перетягивание каната. Для каждого $$$1\leq i \leq n$$$ сила $$$i$$$-го игрока равна $$$s_i$$$. Гвозден будет проводить раунды на выбывание до тех пор, пока не останется один игрок. Мы назовем этого игрока абсолютным победителем.

В каждом раунде:

  • Предположим, что $$$m>1$$$ игроков все еще в игре, где $$$m$$$ является степенью $$$2$$$.
  • Эти $$$m$$$ игроков разбиваются на две команды равных размеров (т. е. по $$$m/2$$$ в каждой команде). Сила команды равна сумме сил всех игроков.
  • Если команды имеют равные значения силы, то Гвозден выбирает, кто выигрывает; иначе выигрывает более сильная команда.
  • Все игроки в проигравшей команде выбывают, и остается $$$m/2$$$ игроков.

Гвозден может выбирать, как образуются команды на в каждом раунде, и команду-победителя в случае равных сил. Гвозден знает силу каждого игрока и ему интересно, кто может стать абсолютным победителем, а кто не может. Ответьте на этот вопрос.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$4 \leq n \leq 32$$$) — количество игроков. Гарантируется, что $$$n$$$ являются степенью $$$2$$$.

Вторая строка содержит последовательность целых чисел $$$s_1,s_2, \ldots, s_n$$$ ($$$1 \leq s_i \leq 10^{15}$$$) — силы игроков.

Выходные данные

В единственной строке выведите бинарную строку $$$s$$$ длины $$$n$$$: $$$i$$$-й символ $$$s$$$ должен быть равен $$$1$$$, если $$$i$$$-й игрок может стать абсолютным победителем, и $$$0$$$ в противном случае.

Примеры
Входные данные
4
60 32 59 87
Выходные данные
1001
Входные данные
4
100 100 100 100
Выходные данные
1111
Входные данные
8
8 8 8 8 4 4 4 4
Выходные данные
11110000
Входные данные
32
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
Выходные данные
00000000000000001111111111111111
Входные данные
16
1 92875987325987 1 1 92875987325986 92875987325985 1 92875987325988 92875987325990 92875987325989 1 1 92875987325984 92875987325983 1 1
Выходные данные
0100110111001000
Примечание

В первом примере игроки $$$1$$$ и $$$4$$$, имеющие силы $$$60$$$ и $$$87$$$, могут стать абсолютными победителями.

Опишем процесс для игрока $$$1$$$. Изначально мы разделим игроков на команды $$$[1,3]$$$ и $$$[2,4]$$$. Силы команд равны $$$60+59=119$$$ и $$$32+87=119$$$. Так как они равны, то Гвозден может выбрать, кто выбывает, пусть это будет вторая команда.

Остаются два игрока $$$1$$$ и $$$3$$$. Так как у $$$1$$$ сила больше ($$$60>59$$$), то он побеждает и становится абсолютным победителем.

В третьем примере силы остающихся игроков может быть $$$[8,8,8,8,4,4,4,4] \rightarrow [8,8,4,4] \rightarrow [8,4] \rightarrow [8]$$$. Любой игрок с силой $$$8$$$ может стать абсолютным победителем, и можно показать, что все остальные не могут.