Недавно Никита провел очень противоречивый раунд, после которого его вклад очень быстро менялся.
Анонс висел на главной странице \(n\) секунд. В \(i\)-ю секунду \(|a_i|\)-й человек либо поставил лайк, либо убрал лайк (в этой задаче Никите повезло и дизлайков не существует). Если \(a_i > 0\), то \(a_i\)-й человек поставил лайк. Если \(a_i < 0\), то \(-a_i\) человек убрал лайк. Каждый человек ставил и убирал лайк не более одного раза. Человек не мог убрать лайк, если он до этого его не ставил.
Так как после раунда у Никиты вклад стал очень плохим, то он захотел проанализировать, как менялся его вклад, пока анонс был на главной странице. Он обратился к создателю платформы с просьбой дать ему последовательность \(a_1, a_2, \ldots, a_n\). Но из-за несовершенства платформы последовательность \(a\) перемешалась.
Вам дана перемешанная последовательность \(a\), которая описывает активность пользователей. Вам требуется сказать для каждого момента от \(1\) до \(n\), какое максимальное и минимальное количество лайков могло быть на посту в этот момент.
Выходные данные
Для каждого набора входных данных выведите по две строки, в каждой из которых по \(n\) чисел.
В первой строке для каждого набора входных данных выведите максимальное количество лайков, которые Никита мог иметь на анонсе в \(i\)-ю секунду.
Во второй строке для каждого набора входных данных выведите минимальное количество лайков, которые Никита мог иметь на анонсе в \(i\)-ю секунду.
Примечание
В первом наборе входных данных максимальные значения достигаются при следующей перестановке: \(1, 2, -2\). А минимальные значения при такой: \(2, -2, 1\).
Во третьем наборе входных данных все максимумы достигаются при следующей перестановке: \(4, 2, 3, 1, -1, -2\). А минимальные значения при следующей перестановке: \(2, -2, 1, -1, 3, 4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
1 2 -2
2
1 -1
6
4 3 -1 2 1 -2
5
4 2 -2 1 3
7
-1 6 -4 3 2 4 1
|
1 2 1
1 0 1
1 0
1 0
1 2 3 4 3 2
1 0 1 0 1 2
1 2 3 4 3
1 0 1 2 3
1 2 3 4 5 4 3
1 0 1 0 1 2 3
|