Сортування вагонів - A
До тупика зі сторони колії 1 (див. рисунок) під'їхав потяг. дозволяється відцепити від потяга один чи відразу декілька перших вагонів і завезти їх у тупик (при бажанні, можна навіть завезти у тупик відразу весь потяг). Після цього частину з цих вагонів вивезти у сторону колії 2. Після цього можно завезти у тупик ще декілька вагонів і снову частину вагонів вивезти у сторону колії 2. І так далі (так, що кажен вагон може лишь один раз заїхати з колії 1 у тупик, а потім один раз виїхати з тупика на колію 2). Заїзджати вагонам у тупик з колії 2 чи виїзжати з тупика на колію 1 забороняється. Не можна з колії 1 потрапити на колію 2, не заїзджаючи у тупик.
Відомо, у якому порядку спочатку йдуть вагони потягу. Потрібно за допомогою вказаних операцій зробити так, щоб вагони потяга йшли по порядку (спочатку перший, потім другий і т.д., рахуючи від голови потяга, який їде по колії 2 у сторону від тупика).
Вхідні дані
Вводиться число N — кількість вагонів у потязі (1 ≤ N ≤ 2000). Далі йдуть номери вагонів у порядку від голови потяга, який їде по колії 1 у сторону тупика. Вагони пронумеровано натуральними числами від 1 до N, кожне з яких зустрічається рівно один раз.
Вихідні дані
Якщо зробити так, щоб вагони йшли у порядку від 1 до N, рахуючи відт голови потягу, коли потяг поїде по колії 2 з тупика, можна, виведіть дії, які потрібно виконати з потягом. Кожна дія описується двома числами: типом та кількістю вагонів:
якщо потрібно завезти з колії 1 у тупик K вагонів, повинно бути виведено спочатку число 1, а потім — число K (K ≥ 1),
якщо потрібно вивезти з тупика на колію 2 K вагонів, повинно бути виведено спочатку число 2, а потім — число K (K ≥ 1).
Якщо можливі декілька послідовстей дій, які призводять до потрібного результату, виведіть довільну з них.
Якщо вишукувати вагони по порядку неможливо, виведіть одне число 0.