DS-S95-CA2-3

Time Limit: 2 Seconds    Memory Limit: 4096 KB

You can find the related question in the course page.


Input

You can find the related input format in the course page.


Output

You can find the related output format in the course page.


Sample Input

5
3 1 4 2 5
6
4 1 2 6 3 5
6
5 3 4 7 6 8
9
5 2 1 3 4 8 7 6 9 
0

Sample Output

Invalid input
 Invalid input 
4 3 6 8 7 5
1 4 3 2 6 7 9 8 5
Submit