시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 714 329 282 49.129%

문제

n개의 정수로 된 순서 S= (s1, s2, ..., sn)가 있다. 여기서 si ≠ sj이고, 1 ≤ si ≤ n이다. S로부터 새로운 순서 R = (r1, r2, ..., rn)을 얻을 수 있는데, 여기서 ri는 S의 부분 순서 {s1, s2, ..., si-2, si-1} 중에서 si보다 작은 수의 개수이다.

n = 10인 경우의 예를 보자. S = (6, 4, 3, 5, 1, 2, 7, 8, 9, 10)이라면 R = (0, 0, 0, 2, 0, 1, 6, 7, 8, 9)이 된다. 어떤 순서 R이 주어질 때, 여러분은 R을 이용하여 S를 찾는 프로그램을 작성하어야 한다. 경우에 따라서는 R로부터 S를 찾는 것이 불가능할 수 있다. 예를 들어, 만약 n = 5이고, R = (0, 2, 2, 0, 1)이라면 이런 R에 대응하는 S는 존재하지 않는다.

입력

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 S에 있는 정수의 개수 n (1 ≤ n ≤ 100)이 주어진다. 그 다음 줄에는 n개의 정수로 된 R이 주어진다. 

출력

출력은 표준출력을 사용한다. 주어진 각 순서 R 에 대해, 대응하는 순서 S 를 찾아 한 줄에 출력하여야 한다. 만약 R로부터 S를 찾는 것이 불가능할 경우에 “IMPOSSIBLE”을 출력한다.

예제 입력 1

3
10
0 0 0 2 0 1 6 7 6 9
10
0 0 0 0 0 0 0 0 0 0
12
0 3 4 5 0 1 2 3 4 5 6 7

예제 출력 1

6 4 3 5 1 2 8 9 7 10
10 9 8 7 6 5 4 3 2 1
IMPOSSIBLE
W3sicHJvYmxlbV9pZCI6IjkwMTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMWNcdWMxMWMiLCJkZXNjcmlwdGlvbiI6IjxwPm5cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1YjQxYyBcdWMyMWNcdWMxMWMgUz0gKHM8c3ViPjE8XC9zdWI+LCBzPHN1Yj4yPFwvc3ViPiwgLi4uLCBzPHN1Yj5uPFwvc3ViPilcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMgczxzdWI+aTxcL3N1Yj4gJm5lOyBzPHN1Yj5qPFwvc3ViPlx1Yzc3NFx1YWNlMCwgMSAmbGU7IHM8c3ViPmk8XC9zdWI+ICZsZTsgblx1Yzc3NFx1YjJlNC4gU1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjMjFjXHVjMTFjIFIgPSAocjxzdWI+MTxcL3N1Yj4sIHI8c3ViPjI8XC9zdWI+LCAuLi4sIHI8c3ViPm48XC9zdWI+KVx1Yzc0NCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVjNWVjXHVhZTMwXHVjMTFjIHI8c3ViPmk8XC9zdWI+XHViMjk0IFNcdWM3NTggXHViZDgwXHViZDg0IFx1YzIxY1x1YzExYyB7czxzdWI+MTxcL3N1Yj4sIHM8c3ViPjI8XC9zdWI+LCAuLi4sIHM8c3ViPmktMjxcL3N1Yj4sIHM8c3ViPmktMTxcL3N1Yj59IFx1YzkxMVx1YzVkMFx1YzExYyBzaVx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+biA9IDEwXHVjNzc4IFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWM2MDhcdWI5N2MgXHViY2Y0XHVjNzkwLiBTID0gKDYsIDQsIDMsIDUsIDEsIDIsIDcsIDgsIDksIDEwKVx1Yzc3NFx1Yjc3Y1x1YmE3NCBSID0gKDAsIDAsIDAsIDIsIDAsIDEsIDYsIDcsIDgsIDkpXHVjNzc0IFx1YjQxY1x1YjJlNC4gXHVjNWI0XHViNWE0IFx1YzIxY1x1YzExYyBSXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMsIFx1YzVlY1x1YjdlY1x1YmQ4NFx1Yzc0MCBSXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYyBTXHViOTdjIFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhY2JkXHVjNmIwXHVjNWQwIFx1YjUzMFx1Yjc3Y1x1YzExY1x1YjI5NCBSXHViODVjXHViZDgwXHVkMTMwIFNcdWI5N2MgXHVjYzNlXHViMjk0IFx1YWM4M1x1Yzc3NCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHViOWNjXHVjNTdkIG4gPSA1XHVjNzc0XHVhY2UwLCBSID0gKDAsIDIsIDIsIDAsIDEpXHVjNzc0XHViNzdjXHViYTc0IFx1Yzc3NFx1YjdmMCBSXHVjNWQwIFx1YjMwMFx1Yzc1MVx1ZDU1OFx1YjI5NCBTXHViMjk0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjUgXHViMzcwXHVjNzc0XHVkMTMwXHViMjk0IFx1ZDQ1Y1x1YzkwMFx1Yzc4NVx1YjgyNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc0MCBUXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWIzNzBcdWM3NzRcdWQxMzBcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDFjXHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzg1XHViODI1IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWIzNzBcdWM3NzRcdWQxMzBcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBTXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMyMThcdWM3NTggXHVhYzFjXHVjMjE4IG4gKDEgJmxlOyBuICZsZTsgMTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IG5cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1YjQxYyBSXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkOWNcdWI4MjVcdWM3NDAgXHVkNDVjXHVjOTAwXHVjZDljXHViODI1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1Y1x1YjJlNC4gXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWMwMSBcdWMyMWNcdWMxMWMgUiBcdWM1ZDAgXHViMzAwXHVkNTc0LCBcdWIzMDBcdWM3NTFcdWQ1NThcdWIyOTQgXHVjMjFjXHVjMTFjIFMgXHViOTdjIFx1Y2MzZVx1YzU0NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzVlY1x1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBSXHViODVjXHViZDgwXHVkMTMwIFNcdWI5N2MgXHVjYzNlXHViMjk0IFx1YWM4M1x1Yzc3NCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NjAgXHVhY2JkXHVjNmIwXHVjNWQwICZsZHF1bztJTVBPU1NJQkxFJnJkcXVvO1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTAxMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik9yZGVyIiwiZGVzY3JpcHRpb24iOiI8cD5XZSBoYXZlIGEgc2VxdWVuY2Ugb2YgbiBpbnRlZ2VycyBTID0gKHM8c3ViPjE8XC9zdWI+LCBzPHN1Yj4yPFwvc3ViPiwgJmhlbGxpcDssIHM8c3ViPm48XC9zdWI+KSwgd2hlcmUgczxzdWI+aTxcL3N1Yj4gJm5lOyBzPHN1Yj5qPFwvc3ViPiBhbmQgMSAmbGU7IHM8c3ViPmk8XC9zdWI+ICZsZTsgbi4gVXNpbmcgUywgd2UgbmV3bHkgZGVmaW5lIGFub3RoZXIgc2VxdWVuY2UgUiA9IChyPHN1Yj4xPFwvc3ViPiwgcjxzdWI+MjxcL3N1Yj4sICZoZWxsaXA7LCByPHN1Yj5uPFwvc3ViPiksIHdoZXJlIHI8c3ViPmk8XC9zdWI+IGlzIGRlZmluZWQgYXMgdGhlIG51bWJlciBvZiBpbnRlZ2VycyB3aGljaCBhcmUgc21hbGxlciB0aGFuIHNpIGFtb25nIHRoZSBpbnRlZ2VycyBpbiB7czxzdWI+MTxcL3N1Yj4sIHM8c3ViPjI8XC9zdWI+LCAmaGVsbGlwOywgc2ktMiwgczxzdWI+aS0xPFwvc3ViPn08XC9wPlxyXG5cclxuPHA+TGV0IHVzIHNob3cgb25lIGV4YW1wbGUgZm9yIG4gPSAxMC4gQXNzdW1lIHRoYXQgUyA9ICg2LCA0LCAzLCA1LCAxLCAyLCA3LCA4LCA5LCAxMCksIHRoZW4gUiBzaG91bGQgYmUgUiA9ICgwLCAwLCAwLCAyLCAwLCAxLCA2LCA3LCA4LCA5KS4gV2hlbiB5b3UgYXJlIGdpdmVuIGEgc2VxdWVuY2UgUiwgd3JpdGUgYSBwcm9ncmFtIHdoaWNoIHJlY29uc3RydWN0cyB0aGUgb3JpZ2luYWwgc2VxdWVuY2UgUy4gSW4gc29tZSBjYXNlcyBpdCBpcyBpbXBvc3NpYmxlIHRvIHJlY29uc3RydWN0IFMgZnJvbSBSLiBGb3IgZXhhbXBsZSwgaWYgbiA9IDUgYW5kIFIgPSAoMCwgMiwgMiwgMCwgMSksIHRoZW4gd2Uga25vdyB0aGF0IGl0IGlzIGltcG9zc2libGUgdG8gcmVjb25zdHJ1Y3QgUyBmcm9tIGl0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhbiBpbnRlZ2VyIG4gKDEgJmxlOyBuICZsZTsgMTAwKSwgdGhlIG51bWJlciBvZiBpbnRlZ2VycyBpbiBTLiBUaGVuIGEgc2VxdWVuY2UgUiBvZiBuIGludGVnZXJzIGlzIGdpdmVuIGluIHRoZSBuZXh0IGxpbmUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gRm9yIGVhY2ggc2VxdWVuY2UgUiwgeW91ciBwcm9ncmFtIHNob3VsZCBmaW5kIHRoZSBjb3JyZXNwb25kaW5nIHNlcXVlbmNlIFMgZnJvbSBSIGFuZCBwcmludCBpdCBpbiBlYWNoIGxpbmUuIElmIHlvdSBjYW5ub3QgcmVjb25zdHJ1Y3QgUyBmcm9tIFIsIHRoZW4geW91ciBwcm9ncmFtIHNob3VsZCBwcmludCAmbGRxdW87SU1QT1NTSUJMRSZyZHF1bzsuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d