На пути к спасению городка Энджел Гроув черный рейнджер Зак Тейлор столкнулся с очередным препятствием. Рейнджер оказался на инопланетном космическом корабле в окружении врагов, и теперь, чтобы освободиться, ему необходимо уничтожить всех врагов в определенном порядке.
Каждый из n врагов обладает силой f
i. Однако среди них имеется главный враг — босс, чья сила равняется сумме сил всех остальных врагов. Так как уничтожение босса требует полной концентрации и сосредоточенности, Зак сможет справиться с ним только после того, как уничтожит всех остальных врагов.
В запасе у рейнджера мало времени, так что он не успевает понять, кто босс. Ему необходима ваша помощь. Восстановите порядок, в котором Заку Тейлору необходимо уничтожать врагов, чтобы выбраться на свободу.
Входные данные
В первой строке находится натуральное число n — количество врагов (3 ≤ n ≤ 10
5).
Во второй строке находятся n целых чисел f
i, задающих силу каждого врага (-10
9 ≤ f
i ≤ 10
9).
Силы врагов заданы в случайном порядке.
Выходные данные
В единственной строке выведите числа f
i в порядке, в котором соответствующие им враги будут уничтожаться рейнджером. Если существует несколько порядков, выведите любой.
Гарантируется, что решение всегда существует, а также существует ровно один враг, который может быть боссом.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
2 5 3 |
2 3 5 |
| 2 |
5
-1 1 0 1 -1 |
-1 1 1 -1 0 |