Ngày xưa có một đứa trẻ tên Kino rất thích du lịch và đã đến nhiều nơi kỳ lạ. Một hôm, cậu đến bên một cây cầu và thấy trên cầu có rất nhiều xe mui trần. Không may, cầu rất hẹp, chỉ đủ cho một xe đi qua theo chiều ngang. Các xe trên cầu không chịu nhường nhau, khiến xe đi từ hai phía đều bị kẹt, không thể qua được.

Sau đó, người xây cầu bổ sung một chức năng mới: xoay một đoạn cầu $180$ độ để các xe mui trần trên đoạn đó quay đầu, như hình dưới đây:

Hình 1. Các xe mui trần 321 sau khi xoay trở thành 123

Như hình trên, các xe 321 gặp các xe 45 trên cầu và gây tắc đường. Lúc này, ta có thể xoay đoạn 321, khiến thứ tự xe trên cầu trở thành 12345 và tất cả cùng hướng, nhờ đó chúng có thể rời cầu. Tất nhiên, đây chỉ là một ví dụ đơn giản. Tình hình trên cầu thực tế phức tạp hơn nhiều, cần xoay nhiều lần mới đưa được về dạng 12345.

Nhưng sau khi thiết kế xong cầu, người thiết kế cũng đi du lịch, và không ai trong số cư dân còn lại biết vận hành cây cầu kỳ diệu này. Vì thế, xe trên cầu ngày càng hỗn loạn, cuối cùng trở thành tình trạng hiện tại. Để qua cầu, Kino tìm được thiết bị điều khiển cùng sách hướng dẫn bên cầu, và tìm lại được cách vận hành. Với sự giúp đỡ của cư dân gần đó, cậu đã sắp xếp thành công các xe theo thứ tự $1,2,3,\ldots$ và cùng hướng. Bạn có biết cậu đã làm thế nào không?

Dữ liệu vào

Đây là bài nộp đáp án. Các tệp đầu vào convertible1.in đến convertible10.in đã có trong thư mục người dùng. Dòng đầu tiên chứa số xe mui trần trên cầu $n$, với các xe được đánh số $1,2,\ldots,n$. Dòng thứ hai mô tả vị trí và hướng của các xe bằng một dãy các giá trị $+i$ hoặc $-i$. Giá trị $-i$ tại vị trí thứ $j$ nghĩa là xe $i$ nằm ở vị trí thứ $j$ trên cầu và hướng sang phải; giá trị $+i$ nghĩa là xe $i$ nằm ở vị trí thứ $j$ và hướng sang trái.

Dữ liệu ra

Bạn phải đặt các tệp đầu ra convertible1.out đến convertible10.out trong thư mục người dùng, không cần nộp chương trình. Dòng đầu tiên chứa số lần xoay $m$. Mỗi dòng trong $m$ dòng tiếp theo mô tả một lần xoay, gồm vị trí biên trái và vị trí biên phải. Đầu ra phải bảo đảm dãy cuối cùng là $1,2,3,\ldots,n$, chứ không phải $-1,-2,-3,\ldots,-n$ hay dãy nào khác.

Ví dụ

Dữ liệu vào 1

5
-3 -2 -1 4 5

Dữ liệu ra 1

1
1 3

Nhiệm vụ con

Mỗi điểm kiểm tra có tối đa 10 điểm. Điểm nhận được phụ thuộc vào tỷ lệ mức độ tốt của đáp án của bạn so với đáp án tham khảo.

Cách kiểm tra chương trình

Bài này cung cấp trình kiểm tra dữ liệu đầu ra convertible_c. Cách chạy như sau:

#./convertible_c 3

Lệnh này kiểm tra tính hợp lệ của convertible3.out.