시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 2291 885 682 46.712%

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

  • 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
  • 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
  • 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

50
30
24
5
28
45
98
52
60

예제 출력 1

5
28
24
45
30
60
52
98
50
W3sicHJvYmxlbV9pZCI6IjU2MzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzRcdWM5YzQgXHVhYzgwXHVjMGM5IFx1ZDJiOFx1YjlhYyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNzc0XHVjOWM0IFx1YWM4MFx1YzBjOSBcdWQyYjhcdWI5YWNcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWMxMzggXHVhYzAwXHVjOWMwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjNzc0XHVjOWM0IFx1ZDJiOFx1YjlhY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWIxNzhcdWI0ZGNcdWM3NTggXHVjNjdjXHVjYWJkIFx1YzExY1x1YmUwY1x1ZDJiOFx1YjlhY1x1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWQwYTRcdWIyOTQgXHViMTc4XHViNGRjXHVjNzU4IFx1ZDBhNFx1YmNmNFx1YjJlNCBcdWM3OTFcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjE3OFx1YjRkY1x1Yzc1OCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjMTFjXHViZTBjXHVkMmI4XHViOWFjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViMTc4XHViNGRjXHVjNzU4IFx1ZDBhNFx1YjI5NCBcdWIxNzhcdWI0ZGNcdWM3NTggXHVkMGE0XHViY2Y0XHViMmU0IFx1ZDA2Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNjdjXHVjYWJkLCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjMTFjXHViZTBjXHVkMmI4XHViOWFjXHViM2M0IFx1Yzc3NFx1YzljNCBcdWFjODBcdWMwYzkgXHVkMmI4XHViOWFjXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3VwbG9hZFwvaW1hZ2VzXC9ic2VhcmNodHJlZS5wbmdcIiBzdHlsZT1cImhlaWdodDoyNDJweDsgd2lkdGg6NDI2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjODA0XHVjNzA0IFx1YzIxY1x1ZDY4YyAoXHViOGU4XHVkMmI4LVx1YzY3Y1x1Y2FiZC1cdWM2MjRcdWI5NzhcdWNhYmQpXHVjNzQwIFx1YjhlOFx1ZDJiOFx1Yjk3YyBcdWJjMjlcdWJiMzhcdWQ1NThcdWFjZTAsIFx1YzY3Y1x1Y2FiZCBcdWMxMWNcdWJlMGNcdWQyYjhcdWI5YWMsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWMxMWNcdWJlMGMgXHVkMmI4XHViOWFjXHViOTdjIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWJjMjlcdWJiMzhcdWQ1NThcdWJhNzRcdWMxMWMgXHViMTc4XHViNGRjXHVjNzU4IFx1ZDBhNFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1ZDZjNFx1YzcwNCBcdWMyMWNcdWQ2OGMgKFx1YzY3Y1x1Y2FiZC1cdWM2MjRcdWI5NzhcdWNhYmQtXHViOGU4XHVkMmI4KVx1YjI5NCBcdWM2N2NcdWNhYmQgXHVjMTFjXHViZTBjXHVkMmI4XHViOWFjLCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjMTFjXHViZTBjXHVkMmI4XHViOWFjLCBcdWI4ZThcdWQyYjggXHViMTc4XHViNGRjIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWQwYTRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM3MDRcdWM3NTggXHVjNzc0XHVjOWM0IFx1YWM4MFx1YzBjOSBcdWQyYjhcdWI5YWNcdWM3NTggXHVjODA0XHVjNzA0IFx1YzIxY1x1ZDY4YyBcdWFjYjBcdWFjZmNcdWIyOTQgNTAgMzAgMjQgNSAyOCA0NSA5OCA1MiA2MCBcdWM3NzRcdWFjZTAsIFx1ZDZjNFx1YzcwNCBcdWMyMWNcdWQ2OGMgXHVhY2IwXHVhY2ZjXHViMjk0IDUgMjggMjQgNDUgMzAgNjAgNTIgOTggNTAgXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM5YzQgXHVhYzgwXHVjMGM5IFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWM4MDRcdWM3MDQgXHVjMjFjXHVkNjhjXHVkNTVjIFx1YWNiMFx1YWNmY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHVkMmI4XHViOWFjXHViOTdjIFx1ZDZjNFx1YzcwNCBcdWMyMWNcdWQ2OGNcdWQ1NWMgXHVhY2IwXHVhY2ZjXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVkMmI4XHViOWFjXHViOTdjIFx1YzgwNFx1YzcwNCBcdWMyMWNcdWQ2OGNcdWQ1NWMgXHVhY2IwXHVhY2ZjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMTc4XHViNGRjXHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWQwYTRcdWM3NTggXHVhYzEyXHVjNzQwIDEwPHN1cD42PFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YWMxMlx1Yzc0MCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWMyMThcdWIyOTQgMTAsMDAwXHVhYzFjIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC4gXHVhYzE5XHVjNzQwIFx1ZDBhNFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWIyOTQgXHViMTc4XHViNGRjXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1Yzc3NFx1YzljNCBcdWFjODBcdWMwYzkgXHVkMmI4XHViOWFjXHViOTdjIFx1ZDZjNFx1YzcwNCBcdWMyMWNcdWQ2OGNcdWQ1NWMgXHVhY2IwXHVhY2ZjXHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NjM5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmluYXJ5IFNlYXJjaCBUcmVlIiwiZGVzY3JpcHRpb24iOiI8cD5BIGJpbmFyeSBzZWFyY2ggdHJlZSBpcyBhIGJpbmFyeSB0cmVlIHRoYXQgc2F0aXNmaWVzIHRoZSBmb2xsb3dpbmcgcHJvcGVydGllczombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgbGVmdCBzdWJ0cmVlIG9mIGEgbm9kZSBjb250YWlucyBvbmx5IG5vZGVzIHdpdGgga2V5cyBsZXNzIHRoYW4gdGhlIG5vZGUmIzM5O3Mga2V5LiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5UaGUgcmlnaHQgc3VidHJlZSBvZiBhIG5vZGUgY29udGFpbnMgb25seSBub2RlcyB3aXRoIGtleXMgZ3JlYXRlciB0aGFuIHRoZSBub2RlJiMzOTtzIGtleS4mbmJzcDs8XC9saT5cclxuXHQ8bGk+Qm90aCB0aGUgbGVmdCBhbmQgcmlnaHQgc3VidHJlZXMgbXVzdCBhbHNvIGJlIGJpbmFyeSBzZWFyY2ggdHJlZXMuJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9ic2VhcmNodHJlZS5wbmdcIiBzdHlsZT1cImhlaWdodDoyNDJweDsgd2lkdGg6NDI2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+UHJlLW9yZGVyIHRyYXZlcnNhbCAoUm9vdC1MZWZ0LVJpZ2h0KSBwcmludHMgb3V0IHRoZSBub2RlJnJzcXVvO3Mga2V5IGJ5IHZpc2l0aW5nIHRoZSByb290IG5vZGUgdGhlbiB0cmF2ZXJzaW5nIHRoZSBsZWZ0IHN1YnRyZWUgYW5kIHRoZW4gdHJhdmVyc2luZyB0aGUgcmlnaHQgc3VidHJlZS4gUG9zdC1vcmRlciB0cmF2ZXJzYWwgKExlZnQmbmRhc2g7UmlnaHQtUm9vdCkgcHJpbnRzIG91dCB0aGUgbGVmdCBzdWJ0cmVlIGZpcnN0IGFuZCB0aGVuIHJpZ2h0IHN1YnRyZWUgYW5kIGZpbmFsbHkgdGhlIHJvb3Qgbm9kZS4gRm9yIGV4YW1wbGUsIHRoZSByZXN1bHRzIG9mIHByZS1vcmRlciB0cmF2ZXJzYWwgYW5kIHBvc3Qtb3JkZXIgdHJhdmVyc2FsIG9mIHRoZSBiaW5hcnkgdHJlZSBzaG93biBpbiBGaWd1cmUgMSBhcmUgYXMgZm9sbG93czombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5QcmUtb3JkZXI6IDUwIDMwIDI0IDUgMjggNDUgOTggNTIgNjAmbmJzcDs8XC9saT5cclxuXHQ8bGk+UG9zdC1vcmRlcjogNSAyOCAyNCA0NSAzMCA2MCA1MiA5OCA1MCZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkdpdmVuIHRoZSBwcmUtb3JkZXIgdHJhdmVyc2FsIG9mIGEgYmluYXJ5IHNlYXJjaCB0cmVlLCB5b3UgdGFzayBpcyB0byBmaW5kIHRoZSBwb3N0LW9yZGVyIHRyYXZlcnNhbCBvZiB0aGlzIHRyZWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUga2V5cyBvZiBhbGwgbm9kZXMgb2YgdGhlIGlucHV0IGJpbmFyeSBzZWFyY2ggdHJlZSBhcmUgZ2l2ZW4gYWNjb3JkaW5nIHRvIHByZS1vcmRlciB0cmF2ZXJzYWwuIEVhY2ggbm9kZSBoYXMgYSBrZXkgdmFsdWUgd2hpY2ggaXMgYSBwb3NpdGl2ZSBpbnRlZ2VyIGxlc3MgdGhhbiAxMDxzdXA+NjxcL3N1cD4uIEFsbCB2YWx1ZXMgYXJlIGdpdmVuIGluIHNlcGFyYXRlIGxpbmVzIChvbmUgaW50ZWdlciBwZXIgbGluZSkuIFlvdSBjYW4gYXNzdW1lIHRoYXQgYSBiaW5hcnkgc2VhcmNoIHRyZWUgZG9lcyBub3QgY29udGFpbiBtb3JlIHRoYW4gMTAsMDAwIG5vZGVzIGFuZCB0aGVyZSBhcmUgbm8gZHVwbGljYXRlIG5vZGVzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgY29udGFpbnMgdGhlIHJlc3VsdCBvZiBwb3N0LW9yZGVyIHRyYXZlcnNhbCBvZiB0aGUgaW5wdXQgYmluYXJ5IHRyZWUuIFByaW50IG91dCBvbmUga2V5IHBlciBsaW5lLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==