Cho dãy a và b gồm n phần tử là hoán vị của n. Bạn được thực hiện thao tác tối đa n lần:
- Chọn 2 số nguyên dương l và r (1 \le l \le r \le n), sau đó đảo ngược đoạn con [l, r] của a.
Nhiệm vụ của bạn là in ra m (0 \le m \le n) là số thao tác và m thao tác bạn cần thực hiện để biến đổi dãy a thành b.
Input and Output
Input
- Số nguyên dương n (1 \le n \le 10^3).
- Dãy a gồm n phần tử a_1, a_2, ..., a_n (1 \le a_i \le n).
- Dãy b gồm n phần tử b_1, b_2, ..., b_n (1 \le b_i \le n).
Output
- In ra m là số thao tác, sau đó là m dòng tương ứng với m thao tác cần thực hiện.
- Nếu có nhiều cách thực hiện thao tác thỏa mãn, hãy in ra một cách bất kì.
Test
Input
5
4 2 3 5 1
1 5 4 2 3
Output
3
3 5
1 3
2 4
Note
- Ngoài cách trên, đảo ngược đoạn [1, 5] rồi đến [1, 3] cũng được tính là đúng.
Bình luận