Эдогава Конан устал разбираться со своими делами и пригласил своего друга, профессора Агасу, в гости. Они решили сыграть в карточную игру. У Конана есть n карт, на i-й из которых записано число ai.
Игроки ходят по очереди, первым ходит Конан. На каждом ходу игрок выбирает карту и выбрасывает её. Кроме того, он выбрасывает все карты, на которых число меньше, чем на выбранной. Формально, если игрок выбирает карту с номером i, он выбрасывает эту карту, а также все карты с номерами j для всех j таких, что aj < ai.
Игрок проигрывает, если он не может сделать ход, то есть если не осталось карт. Определите победителя, если игроки играют оптимально.
Примечание
В первом тестовом примере Конан может выбрать карту с числом 7 и тем самым выкинуть все карты. После этого Агаса проиграет.
Во втором тестовом примере вне зависимости от хода Конана останется одна карта, которую выбросит Агава, после чего карт не останется и Конан проиграет.