시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB169786848.227%

문제

서로 다른 크기의 n개의 팬케이크가 쌓여 있다. 순서 없이 마구 쌓여져있는 팬케이크를 크기 순대로 쌓으려고 한다. 가장 위에는 제일 작은 크기의 팬케이크가 있어야 되고, 가장 아래에는 제일 큰 크기의 팬케이크가 있어야 한다.

팬케이크를 뒤집는 방법은 위에서 k개의 순서를 뒤집는 것이다. 따라서 k번째 팬케이크가 가장 위로 올라오게 되고, 제일 위에 있던 팬케이크는 k번째가 된다.

다음 예를 보자.

팬케이크가 쌓여있는 상태가 주어졌을 때, 이를 순서대로 만드는 방법을 찾아 출력하는 프로그램을 작성하시오. 팬케이크는 최대 max(0, 2n-3)번 뒤집을 수 있다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 숫자 여러개가 공백으로 구분되어있다. 첫 번째 숫자는 팬케이크의 개수 N이고, 그 다음 N개의 숫자는 팬케이크의 크기이다. 가장 위에 있는 팬케이크가 첫 숫자이고, 마지막 숫자는 제일 아래에 있는 팬케이크이다.  N은 30보다 작거나 같다. 팬케이크의 크기는 서로 다르며, 1보다 크거나 같고, N보다 작거나 같다.

출력

각 테스트 케이스에 대해 한 줄에 하나씩 뒤집는 방법을 출력한다. 제일 먼저 뒤집는 횟수 K를 출력한다. 그 다음 뒤집는 방법을 순서대로 출력하면 된다. 뒤집는 방법이 여러개일 때는, 아무거나 출력하면 된다.

예제 입력 1

2
3 1 3 2
5 4 3 2 5 1

예제 출력 1

3 2 3 2
3 3 4 5
W3sicHJvYmxlbV9pZCI6IjI3NTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMmNcdWNmMDBcdWM3NzRcdWQwNmMgXHViNGE0XHVjOWQxXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1ZDA2Y1x1YWUzMFx1Yzc1OCBuXHVhYzFjXHVjNzU4IFx1ZDMyY1x1Y2YwMFx1Yzc3NFx1ZDA2Y1x1YWMwMCZuYnNwO1x1YzMxM1x1YzVlYyBcdWM3ODhcdWIyZTQuIFx1YzIxY1x1YzExYyBcdWM1YzZcdWM3NzQgXHViOWM4XHVhZDZjIFx1YzMxM1x1YzVlY1x1YzgzOFx1Yzc4OFx1YjI5NCBcdWQzMmNcdWNmMDBcdWM3NzRcdWQwNmNcdWI5N2MgXHVkMDZjXHVhZTMwIFx1YzIxY1x1YjMwMFx1Yjg1YyBcdWMzMTNcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNWQwXHViMjk0IFx1YzgxY1x1Yzc3YyBcdWM3OTFcdWM3NDAgXHVkMDZjXHVhZTMwXHVjNzU4IFx1ZDMyY1x1Y2YwMFx1Yzc3NFx1ZDA2Y1x1YWMwMCZuYnNwO1x1Yzc4OFx1YzViNFx1YzU3YyBcdWI0MThcdWFjZTAsIFx1YWMwMFx1YzdhNSBcdWM1NDRcdWI3OThcdWM1ZDBcdWIyOTQgXHVjODFjXHVjNzdjIFx1ZDA3MCBcdWQwNmNcdWFlMzBcdWM3NTggXHVkMzJjXHVjZjAwXHVjNzc0XHVkMDZjXHVhYzAwIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDMyY1x1Y2YwMFx1Yzc3NFx1ZDA2Y1x1Yjk3YyBcdWI0YTRcdWM5ZDFcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1YzcwNFx1YzVkMFx1YzExYyBrXHVhYzFjXHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWI0YTRcdWM5ZDFcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMga1x1YmM4OFx1YzlmOCBcdWQzMmNcdWNmMDBcdWM3NzRcdWQwNmNcdWFjMDAmbmJzcDtcdWFjMDBcdWM3YTUgXHVjNzA0XHViODVjIFx1YzYyY1x1Yjc3Y1x1YzYyNFx1YWM4YyBcdWI0MThcdWFjZTAsIFx1YzgxY1x1Yzc3YyBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMzU4IFx1ZDMyY1x1Y2YwMFx1Yzc3NFx1ZDA2Y1x1YjI5NCBrXHViYzg4XHVjOWY4XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzYwOFx1Yjk3YyBcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZGFkOGZiMzItZGEzYi00MGYxLWFjMzUtNjNlZWMzYWI2NmExXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA1NzVweDsgaGVpZ2h0OiAxMThweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVkMzJjXHVjZjAwXHVjNzc0XHVkMDZjXHVhYzAwIFx1YzMxM1x1YzVlY1x1Yzc4OFx1YjI5NCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0XHViOTdjIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1Y2MzZVx1YzU0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVkMzJjXHVjZjAwXHVjNzc0XHVkMDZjXHViMjk0IFx1Y2Q1Y1x1YjMwMCBtYXgoMCwgMm4tMylcdWJjODggXHViNGE0XHVjOWQxXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWMyMmJcdWM3OTAgXHVjNWVjXHViN2VjXHVhYzFjXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViMjk0IFx1ZDMyY1x1Y2YwMFx1Yzc3NFx1ZDA2Y1x1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NFx1YWNlMCwgXHVhZGY4IFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWQzMmNcdWNmMDBcdWM3NzRcdWQwNmNcdWM3NTggXHVkMDZjXHVhZTMwXHVjNzc0XHViMmU0LiBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWQzMmNcdWNmMDBcdWM3NzRcdWQwNmNcdWFjMDAgXHVjY2FiIFx1YzIyYlx1Yzc5MFx1Yzc3NFx1YWNlMCwgXHViOWM4XHVjOWMwXHViOWM5IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWM4MWNcdWM3N2MgXHVjNTQ0XHViNzk4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWQzMmNcdWNmMDBcdWM3NzRcdWQwNmNcdWM3NzRcdWIyZTQuICZuYnNwO05cdWM3NDAgMzBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC4gXHVkMzJjXHVjZjAwXHVjNzc0XHVkMDZjXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc0XHViYTcwLCAxXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIE5cdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHViNGE0XHVjOWQxXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzgxY1x1Yzc3YyBcdWJhM2NcdWM4MDAgXHViNGE0XHVjOWQxXHViMjk0IFx1ZDY5Zlx1YzIxOCBLXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWI0YTRcdWM5ZDFcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LiBcdWI0YTRcdWM5ZDFcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0IFx1YzVlY1x1YjdlY1x1YWMxY1x1Yzc3YyBcdWI1NGNcdWIyOTQsIFx1YzU0NFx1YmIzNFx1YWM3MFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI3NTkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGbGlwcGluZyBQYW5jYWtlcyIsImRlc2NyaXB0aW9uIjoiPHA+V2Ugc3RhcnQgd2l0aCBhIHN0YWNrIG4gb2YgcGFuY2FrZXMgb2YgZGlzdGluY3Qgc2l6ZXMuIFRoZSBwcm9ibGVtaXMgdG8gY29udmVydCB0aGUgc3RhY2sgdG8gb25lIGluIHdoaWNoIHRoZSBwYW5jYWtlcyBhcmUgaW4gc2l6ZSBvcmRlciB3aXRoIHRoZSBzbWFsbGVzdCBvbiB0aGUgdG9wIGFuZCB0aGUgbGFyZ2VzdCBvbiB0aGUgYm90dG9tLiBUbyBkbyB0aGlzLCB3ZSBhcmUgYWxsb3dlZCB0byBmbGlwIHRoZSB0b3AgayBwYW5jYWtlcyBvdmVyIGFzIGEgdW5pdCAoc28gdGhlIGstdGggcGFuY2FrZSBpcyBub3cgb24gdG9wIGFuZCB0aGUgcGFuY2FrZSBwcmV2aW91c2x5IG9uIHRvcCBpcyBub3cgaW4gdGhlIGstdGggcG9zaXRpb24pLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZTo8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9kYWQ4ZmIzMi1kYTNiLTQwZjEtYWMzNS02M2VlYzNhYjY2YTFcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDU3NXB4OyBoZWlnaHQ6IDExOHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5UaGlzIHByb2JsZW0gaXMgdG8gd3JpdGUgYSBwcm9ncmFtLCB3aGljaCBmaW5kcyBhIHNlcXVlbmNlIG9mIGF0IG1vc3QgbWF4KDAsIDJuICZuZGFzaDsgMykgZmxpcHMsIHdoaWNoIGNvbnZlcnRzIGEgZ2l2ZW4gc3RhY2sgb2YgcGFuY2FrZXMgdG8gYSBzb3J0ZWQgc3RhY2suPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIGxpbmUgb2YgdGhlIGlucHV0IGdpdmVzIGEgc2VwYXJhdGUgZGF0YSBzZXQgYXMgYSBzZXF1ZW5jZSBvZiBudW1iZXJzIHNlcGFyYXRlZCBieSBzcGFjZXMuIFRoZSBmaXJzdCBudW1iZXIgb24gZWFjaCBsaW5lIGdpdmVzIHRoZSBudW1iZXIsIE4sIG9mIHBhbmNha2VzIGluIHRoZSBkYXRhIHNldC4gVGhlIGlucHV0IGVuZHMgd2hlbiBOaXMgMCAoemVybykgd2l0aCBubyBvdGhlciBkYXRhIG9uIHRoZSBsaW5lLiBUaGUgcmVtYWluZGVyIG9mIHRoZSBkYXRhIHNldCBhcmUgdGhlIG51bWJlcnMgMSB0aHJvdWdoIE4gaW4gc29tZSBvcmRlciBnaXZpbmcgdGhlIGluaXRpYWwgcGFuY2FrZSBzdGFjay4gVGhlIG51bWJlcnMgaW5kaWNhdGUgdGhlIHJlbGF0aXZlIHNpemVzIG9mIHRoZSBwYW5jYWtlcy4gTiB3aWxsIGJlLCBhdCBtb3N0LCAzMC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCwgdGhlIG91dHB1dCBpcyBhIHNpbmdsZS1zcGFjZSBzZXBhcmF0ZWQgc2VxdWVuY2Ugb2YgbnVtYmVycyBvbiBhIGxpbmUuIFRoZSBmaXJzdCBudW1iZXIgb24gZWFjaCBsaW5lLCBLLCBnaXZlcyB0aGUgbnVtYmVyIG9mIGZsaXBzIHJlcXVpcmVkIHRvIHNvcnQgdGhlIHBhbmNha2VzLiBUaGlzIG51bWJlciBpcyBmb2xsb3dlZCBieSBhIHNlcXVlbmNlIG9mIEsgbnVtYmVycywgZWFjaCBvZiB3aGljaCBnaXZlcyB0aGUgbnVtYmVyIG9mIHBhbmNha2VzIHRvIGZsaXAgb24gdGhlIGNvcnJlc3BvbmRpbmcgc29ydGluZyBzdGVwLiBUaGVyZSBtYXkgYmUgc2V2ZXJhbCBjb3JyZWN0IHNvbHV0aW9ucyBmb3Igc29tZSBkYXRhc2V0cy4gRm9yIGluc3RhbmNlIDMgMyAyIDMgaXMgYWxzbyBhIHNvbHV0aW9uIHRvIHRoZSBmaXJzdCBwcm9ibGVtIGJlbG93LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=