문제
상근이네 마을의 울타리는 모두 높이가 다른 N개의 판자로 만든다. 상근이는 아직 울타리를 가지고 있지 않았기 때문에, 이번 기회에 만들기로 했다.
나무 판자는 109보다 작은 양의 정수로 나타낼 수 있다. 이 정수는 판자의 높이를 나타낸다.
울타리의 매력도는 인접한 판자의 높이 차이의 합이다.
상근이는 이미 나무 판자를 상점에서 사왔다. 하지만, 어떠한 순서로 울타리를 만들어야 하는지 결정하지 못했다. 결국 상근이는 동규의 울타리와 비슷하게 울타리를 만들려고 한다. 그러면서 매력도를 가능한 크게 만들려고 한다.
인접한 두 나무 판자의 높이의 대소관계가 일치한다면, 두 울타리가 비슷하다고 한다. 즉, 두 울타리 모두 i번 판자가 (i+1)번 판자보다 커야(작아야) 한다.
동규의 울타리의 높이와 상근이가 구매한 나무 판자의 높이가 주어졌을 때, 동규의 울타리와 비슷하면서 매력도가 가장 큰 울타리를 만드는 프로그램을 작성하시오.
상근이의 울타리의 높이가 모두 각각 다르고, 동규의 울타리의 높이가 모두 각각 다르다.
출력
첫째 줄에 상근이의 울타리의 매력도를 출력한다.
둘째 줄에 상근이의 울타리를 구성하는 나무 판자의 높이를 공백으로 구분해 출력한다.
예제 출력 2
3010
100 80 10 40 50 1000 20 70 500 30
W3sicHJvYmxlbV9pZCI6IjI4MTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5ZTRcdWI4MjVcdWM3ODhcdWIyOTQgXHVjNmI4XHVkMGMwXHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIxMjQgXHViOWM4XHVjNzQ0XHVjNzU4IFx1YzZiOFx1ZDBjMFx1YjlhY1x1YjI5NCBcdWJhYThcdWI0NTAgXHViMTkyXHVjNzc0XHVhYzAwIFx1YjJlNFx1Yjk3OCBOXHVhYzFjXHVjNzU4IFx1ZDMxMFx1Yzc5MFx1Yjg1YyBcdWI5Y2NcdWI0ZTBcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM1NDRcdWM5YzEgXHVjNmI4XHVkMGMwXHViOWFjXHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWM5YzAgXHVjNTRhXHVjNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjNzc0XHViYzg4IFx1YWUzMFx1ZDY4Y1x1YzVkMCBcdWI5Y2NcdWI0ZTRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIwOThcdWJiMzQgXHVkMzEwXHVjNzkwXHViMjk0IDEwPHN1cD45PFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YzgxNVx1YzIxOFx1YjI5NCBcdWQzMTBcdWM3OTBcdWM3NTggXHViMTkyXHVjNzc0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNmI4XHVkMGMwXHViOWFjXHVjNzU4IFx1YjllNFx1YjgyNVx1YjNjNFx1YjI5NCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVkMzEwXHVjNzkwXHVjNzU4IFx1YjE5Mlx1Yzc3NCBcdWNjMjhcdWM3NzRcdWM3NTggXHVkNTY5XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzc0XHViYmY4IFx1YjA5OFx1YmIzNCBcdWQzMTBcdWM3OTBcdWI5N2MgXHVjMGMxXHVjODEwXHVjNWQwXHVjMTFjIFx1YzBhY1x1YzY1NFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWM1YjRcdWI1YTBcdWQ1NWMgXHVjMjFjXHVjMTFjXHViODVjIFx1YzZiOFx1ZDBjMFx1YjlhY1x1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM1N2MgXHVkNTU4XHViMjk0XHVjOWMwIFx1YWNiMFx1YzgxNVx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1ODhcdWIyZTQuIFx1YWNiMFx1YWQ2ZCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViM2Q5XHVhZGRjXHVjNzU4IFx1YzZiOFx1ZDBjMFx1YjlhY1x1YzY0MCBcdWJlNDRcdWMyYjdcdWQ1NThcdWFjOGMgXHVjNmI4XHVkMGMwXHViOWFjXHViOTdjIFx1YjljY1x1YjRlNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YmE3NFx1YzExYyBcdWI5ZTRcdWI4MjVcdWIzYzRcdWI5N2MgXHVhYzAwXHViMmE1XHVkNTVjIFx1ZDA2Y1x1YWM4YyBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzhcdWM4MTFcdWQ1NWMgXHViNDUwIFx1YjA5OFx1YmIzNCBcdWQzMTBcdWM3OTBcdWM3NTggXHViMTkyXHVjNzc0XHVjNzU4IFx1YjMwMFx1YzE4Y1x1YWQwMFx1YWNjNFx1YWMwMCBcdWM3N2NcdWNlNThcdWQ1NWNcdWIyZTRcdWJhNzQsIFx1YjQ1MCBcdWM2YjhcdWQwYzBcdWI5YWNcdWFjMDAgXHViZTQ0XHVjMmI3XHVkNTU4XHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWI0NTAgXHVjNmI4XHVkMGMwXHViOWFjIFx1YmFhOFx1YjQ1MCBpXHViYzg4IFx1ZDMxMFx1Yzc5MFx1YWMwMCAoaSsxKVx1YmM4OCBcdWQzMTBcdWM3OTBcdWJjZjRcdWIyZTQgXHVjZWU0XHVjNTdjKFx1Yzc5MVx1YzU0NFx1YzU3YykgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzZDlcdWFkZGNcdWM3NTggXHVjNmI4XHVkMGMwXHViOWFjXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YzY0MCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVhZDZjXHViOWU0XHVkNTVjIFx1YjA5OFx1YmIzNCBcdWQzMTBcdWM3OTBcdWM3NTggXHViMTkyXHVjNzc0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjNkOVx1YWRkY1x1Yzc1OCBcdWM2YjhcdWQwYzBcdWI5YWNcdWM2NDAgXHViZTQ0XHVjMmI3XHVkNTU4XHViYTc0XHVjMTFjIFx1YjllNFx1YjgyNVx1YjNjNFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzZiOFx1ZDBjMFx1YjlhY1x1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzZiOFx1ZDBjMFx1YjlhY1x1Yzc1OCBcdWIxOTJcdWM3NzRcdWFjMDAgXHViYWE4XHViNDUwIFx1YWMwMVx1YWMwMSBcdWIyZTRcdWI5NzRcdWFjZTAsIFx1YjNkOVx1YWRkY1x1Yzc1OCBcdWM2YjhcdWQwYzBcdWI5YWNcdWM3NTggXHViMTkyXHVjNzc0XHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWFjMDFcdWFjMDEgXHViMmU0XHViOTc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMzAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzZDlcdWFkZGNcdWM3NTggXHVjNmI4XHVkMGMwXHViOWFjXHViOTdjIFx1YWQ2Y1x1YzEzMVx1ZDU1OFx1YjI5NCBcdWQzMTBcdWM3OTBcdWM3NTggXHViMTkyXHVjNzc0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVhZDZjXHViOWU0XHVkNTVjIFx1ZDMxMFx1Yzc5MFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzZiOFx1ZDBjMFx1YjlhY1x1Yzc1OCBcdWI5ZTRcdWI4MjVcdWIzYzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWM2YjhcdWQwYzBcdWI5YWNcdWI5N2MgXHVhZDZjXHVjMTMxXHVkNTU4XHViMjk0IFx1YjA5OFx1YmIzNCBcdWQzMTBcdWM3OTBcdWM3NTggXHViMTkyXHVjNzc0XHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NzQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI4MTMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJPR1JBREEiLCJkZXNjcmlwdGlvbiI6IjxwPkluIE1pcmtvJnJzcXVvO3MgdmlsbGFnZSBhbGwgZmVuY2VzIGFyZSBtYWRlIG9mIGV4YWN0bHkgTiBib2FyZHMgd2l0aCBkaWZmZXJlbnQgaGVpZ2h0cy4gTWlya28gZG9lc24mcnNxdW87dCBoYXZlIGhpcyBvd24gZmVuY2UgeWV0LCBzbyBoZSBkZWNpZGVkIHRvIGJ1aWxkIG9uZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBib2FyZCBpcyByZXByZXNlbnRlZCBieSBhIHBvc2l0aXZlIGludGVnZXIgbGVzcyB0aGFuIDEwPHN1cD45PFwvc3VwPiAtIGl0JnJzcXVvO3MgaGVpZ2h0LiBXZSBkZWZpbmUgdGhlIG5pY2VuZXNzIG9mIHRoZSBmZW5jZSBhcyBhIHN1bSBvZiBoZWlnaHQgZGlmZmVyZW5jZXMgYmV0d2VlbiBhZGphY2VudCBib2FyZHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1pcmtvIGFscmVhZHkgYm91Z2h0IHRoZSBib2FyZHMsIGJ1dCBoZSBkb2VzbiZyc3F1bzt0IGtub3cgaG93IHRvIG9yZGVyIHRoZW0gaW50byBhIGZlbmNlLiBIZSB3b3VsZCBsaWtlIGhpcyBmZW5jZSB0byBiZSBzaW1pbGFyIHRvIFNsYXZrbyZyc3F1bztzIGZlbmNlLCBidXQgYWxzbyB0byBiZSBhcyBuaWNlIGFzIHBvc3NpYmxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5XZSBzYXkgdGhhdCB0d28gZmVuY2VzIGFyZSBzaW1pbGFyIGlmIG9yZGVyaW5nIG9mIGFkamFjZW50IGJvYXJkcyBpcyB0aGUgc2FtZSBpbiBib3RoIGZlbmNlcywgaS5lLiBpZiBpLXRoIGJvYXJkIG9mIG9uZSBmZW5jZSBpcyBzbWFsbGVyIChvciBsYXJnZXIpIHRoYW4gKGkrMSktc3QsIHRoYW4gdGhlIHNhbWUgbXVzdCBob2xkIGZvciB0aGF0IGJvYXJkcyBvZiB0aGUgb3RoZXIgZmVuY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkdpdmVuIFNsYXZrbyZyc3F1bztzIGZlbmNlIGNvbmZpZ3VyYXRpb24sIGFuZCBoZWlnaHRzIG9mIGJvYXJkcyB0aGF0IE1pcmtvIGJvdWdodCwgcHV0IE1pcmtvJnJzcXVvO3MgZmVuY2UgdG9nZXRoZXIgc28gdGhhdCBpdCBpcyBzaW1pbGFyIHRvIFNsYXZrbyZyc3F1bztzIGJ1dCBhbHNvIGFzIG5pY2UgYXMgcG9zc2libGUuIElmIHRoZXJlIGlzIG1vcmUgdGhhbiBvbmUgc29sdXRpb24sIG91dHB1dCBhbnkgb2YgdGhlbS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGludGVnZXIgTiAoMiAmbGU7IE4gJmxlOyAzMDAgMDAwKSwgbnVtYmVyIG9mIGJvYXJkcyBpbiBlYWNoIGZlbmNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIGxpbmUgY29uYXRpbnMgTiBkaWZmZXJlbnQgcG9zaXRpdmUgaW50ZWdlcnMgcmVwcmVzZW50aW5nIFNsYXZrbyZyc3F1bztzIGZlbmNlLjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIGxpbmUgY29udGFpbnMgTiBkaWZmZXJlbnQgcG9zaXRpdmUgaW50ZWdlcnMgcmVwcmVzZW50aW5nIGhlaWdodHMgb2YgYm9hcmRzIE1pcmtvIGJvdWdodCBmb3IgaGlzIGZlbmNlLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgbWF4aW11bSBwb3NzaWJsZSBuaWNlbmVzcyBvZiBNaXJrbyZyc3F1bztzIGZlbmNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIGxpbmUgc2hvdWxkIGNvbnRhaW4gTiBpbnRlZ2VycywgTWlya28mcnNxdW87cyBib2FyZHMgaW4gb3B0aW1hbCBvcmRlciBhcyBkZXNjcmliZWQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==