Berland Music — это стриминговый сервис, созданный специально для поддержки локальных Берляндских исполнителей. Его разработчики в данный момент работают над модулем рекомендаций песен.
Представим, что Монокарпу порекомендовали \(n\) песен, пронумерованных от \(1\) до \(n\). У \(i\)-й песни предсказанный рейтинг равен \(p_i\), где \(1 \le p_i \le n\) и каждое целое число от \(1\) до \(n\) встречается ровно один раз. Другими словами, \(p\) — перестановка.
После прослушивания каждой песни Монокарп ее оценил — понравилась она ему или нет. Последовательность его оценок представлена строкой \(s\) такой, что \(s_i=0\) значит, что ему не понравилась \(i\)-я песня, а \(s_i=1\) значит, что понравилась.
Теперь сервису надо пересчитать рейтинги песен так, чтобы:
- новые рейтинги \(q_1, q_2, \dots, q_n\) все еще были перестановкой (\(1 \le q_i \le n\); каждое целое число от \(1\) до \(n\) встречается ровно один раз);
- каждая песня, которая понравилась Монокарпу, имеет рейтинг больше каждой, которая ему не понравилась (формально, для всех \(i, j\) таких, что \(s_i=1\) и \(s_j=0\), выполняется \(q_i>q_j\)).
Среди всех корректных перестановок \(q\) найдите такую, у которой значение \(\sum\limits_{i=1}^n |p_i-q_i|\) наименьшее, где \(|x|\) — это абсолютное значение \(x\).
Выведите перестановку \(q_1, q_2, \dots, q_n\). Если существует несколько ответов, выведите любой из них.
Выходные данные
На каждый набор входных данных выведите перестановку \(q\) — пересчитанные рейтинги песен. Если существует несколько ответов таких, что \(\sum\limits_{i=1}^n |p_i-q_i|\) минимально, выведите любой из них.
Примечание
В первом наборе входных данных существует только одна перестановка \(q\) такая, что каждая понравившаяся песня имеет рейтинг выше, чем каждая не понравившаяся: песня \(1\) получает рейтинг \(2\), а песня \(2\) — рейтинг \(1\). \(\sum\limits_{i=1}^n |p_i-q_i|=|1-2|+|2-1|=2\).
Во втором наборе входных данных Монокарпу понравились все песни, поэтому корректны все перестановки. Перестановка с минимальной суммой абсолютных разностей равна перестановке \(p\). Ее стоимость равна \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
1 2
10
3
3 1 2
111
8
2 3 1 8 5 4 7 6
01110001
|
2 1
3 1 2
1 6 5 8 3 2 4 7
|