Колись жив хлопчик на ім’я Kino, який дуже любив подорожувати й побував у багатьох дивовижних місцях. Одного дня він підійшов до великого мосту й побачив, що на ньому стоїть багато кабріолетів. На жаль, міст був вузьким: по ширині міг проїхати лише один кабріолет. Машини на мосту не поступалися одна одній, тому автомобілі з обох напрямків застрягли й не могли проїхати.
Згодом будівельник додав мосту нову можливість: повертати деяку його ділянку на $180$ градусів, розвертаючи кабріолети на ній, як показано нижче:
Рисунок 1. Після повороту кабріолети $3,2,1$ утворюють порядок $1,2,3$.
Як показано на рисунку, кабріолети $3,2,1$ зустрілися на мосту з кабріолетами $4,5$, утворивши затор. Можна повернути ділянку з машинами $3,2,1$, після чого порядок кабріолетів на мосту стане $1,2,3,4,5$, а всі вони будуть спрямовані однаково й зможуть з’їхати з мосту. Звісно, це лише простий приклад. На справжньому мосту ситуація значно складніша, і для отримання порядку $1,2,3,4,5$ потрібно багато поворотів.
Однак після проєктування мосту його конструктор теж вирушив у подорож, і серед мешканців, що залишилися, ніхто не вмів керувати цим чарівним мостом. Тому рух на ньому ставав дедалі хаотичнішим, аж поки одного дня не склалася теперішня ситуація. Щоб перейти міст, Kino знайшов біля нього пристрій керування та інструкцію й знову відкрив спосіб керування мостом. За допомогою місцевих мешканців він успішно розташував кабріолети в порядку $1,2,3,\ldots$, спрямувавши їх усі однаково. Чи знаєте ви, як він це зробив?
Вхідні дані
У цій задачі потрібно подати лише відповіді. Вхідні файли convertible1.in–convertible10.in уже розміщено в каталозі користувача. Перший рядок вхідного файлу містить кількість кабріолетів на мосту $n$; вони мають номери $1,2,\ldots,n$. Другий рядок задає розташування й напрямки кабріолетів послідовністю значень $+i$ або $-i$. Значення $-i$ на позиції $j$ означає, що на позиції $j$ мосту стоїть кабріолет $i$, спрямований праворуч; значення $+i$ на позиції $j$ означає, що там стоїть кабріолет $i$, спрямований ліворуч.
Вихідні дані
Потрібно розмістити вихідні файли convertible1.out–convertible10.out у каталозі користувача, а подавати програму не потрібно. Перший рядок вихідного файлу містить кількість поворотів $m$. Кожен із наступних $m$ рядків описує один поворот і містить позиції його лівої та правої меж. Ваші вихідні дані мають забезпечувати кінцеву послідовність $1,2,3,\ldots,n$, а не $-1,-2,-3,\ldots,-n$ чи будь-яку іншу.
Приклади
Вхідні дані 1
5 -3 -2 -1 4 5
Вихідні дані 1
1 1 3
Оцінювання
Максимальна оцінка за кожний тест становить 10 балів. Оцінка залежить від співвідношення якості вашого результату та еталонної відповіді.
Як перевірити вашу програму
Для цієї задачі надається перевіряльник вихідних даних convertible_c. Його запускають так:
#./convertible_c 3
Це перевіряє коректність файлу convertible3.out.