Коля очень любит играть в космонавтов. Правда сегодня он выбрал игру еще более космического масштаба и играет в большие космические объекты. Его игра выглядит так: В космосе на отрезке находятся n метеоритов. Для каждого метеорита известна его масса, и в зависимости от знака при массе, метеориты летят влево (при знаке минус), или же вправо. При столкновении метеорит с меньшей массой взрывается, при одинаковой массе уничтожаются оба метеорита. При этом метеоритов с нулевой массой не бывает. Узнайте, какие метеориты уцелели и выведите их в том же порядке, в котором они были изначально, чтобы Коле быстрее доиграть в игру, потому что ему уже пора идти обедать.. Входные данные В первой строке задано число n — количество метеоритов. (1⩽n⩽10е6). Во второй строке дано n чисел — массы и направления движения метеоритов. (−10е9⩽ai⩽10е9, ai≠0). Выходные данные Выведите две строки: на первой количество уцелевших метеоритов, на второй массы и направления оставшихся метеоритов после всех столкновений. Порядок вывода метеоритов должен совпадать с их изначальным расположением. Примеры входные данные 3 10 2 -5 выходные данные 1 10 входные данные 5 -5 1 -1 4 -3 выходные данные 2 -5 4 входные данные 2 8 -8 выходные данные 0
Префиксная форма записи заключается в том, что сначала записывается операция, потом префиксная запись её первого аргумента, потом второго аргумента. Это соответствует обходу дерева сверху вниз и слева направо, записываем, что сверху, потом идем вниз. Вот что получится в итоге:
а) * + a b + c * 2 d
б) + * - * 2 a * 3 d c * 2 b
в) - * 3 a * + * 2 b c d
В постфиксной записи, наоборот, записываются сначала аргументы, потом операция. Это соответствует обходу дерева снизу-вверх.
а) a b + c 2 d * + *
б) 2 a * 3 d * - c * 2 b * +
в) 3 a * 2 b * c + d * -