Любите ли вы лето? Жители Берляндии любят. А особенно они любят в жаркую летнюю погоду полакомиться мороженым. Так и в этот летний день перед киоском с мороженым образовалась огромная очередь из n берляндцев. Известно, что у каждого из них есть с собой некоторая сумма берляндских долларов. Жители Берляндии сговорчивые, поэтому каждый берляндец всего за 1 доллар согласен поменяться местом с тем, кто стоит в очереди непосредственно за ним. Более формально, если человек a стоял сразу за человеком b, то человек a может заплатить человеку b 1 доллар, и тогда a и b поменяются местами. Разумеется, если у человека a нулевое количество долларов, то он не может поменяться местами с b.

Жители Берляндии — люди странные. В частности, они расстраиваются, когда в очереди перед ними стоит кто-то со строго меньшей суммой денег.

Сможете ли вы помочь жителям Берляндии упорядочиться в очереди так, чтобы все они были счастливы? Счастливый берляндец — это тот, который стоит в очереди первым, либо тот, впереди которого стоит другой житель с не меньшим количеством долларов. Учтите, что берляндцы — люди принципиальные, и согласны меняться местами только указанным выше способом.