시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 92 29 24 31.579%

문제

수열 a1, ..., an이 주어졌을 때, reduce(i)는 ai와 ai+1를 max(ai, ai+1)로 바꾸는 연산이다. 이 연산을 사용하면 수열의 길이는 1만큼 작아지게 된다.

reduce연산의 비용은 max(ai, ai+1)과 같다. 연산을 n-1번 사용하면, 수열의 길이는 1이 된다.

reduce연산을 n-1번 사용해서, 수열의 길이를 1로 만들 때, 연산의 비용의 합의 최소값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 길이 n(1 ≤ n ≤ 1,000,000)이 주어진다. 다음 n개의 줄에는 수열의 원소 ai가 순서대로 주어진다. (0 ≤ ai ≤ 1,000,000,000)

출력

첫째 줄에 수열의 길이를 1로 만드는데 드는 비용의 합의 최소값을 출력한다.

예제 입력 1

3
1
2
3

예제 출력 1

5
W3sicHJvYmxlbV9pZCI6IjMzNjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWM1ZjQgXHVjOTA0XHVjNzc0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWMyMThcdWM1ZjQgYTxzdWI+MTxcL3N1Yj4sIC4uLiwgYTxzdWI+bjxcL3N1Yj5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgcmVkdWNlKGkpXHViMjk0IGE8c3ViPmk8XC9zdWI+XHVjNjQwIGE8c3ViPmkrMTxcL3N1Yj5cdWI5N2MgbWF4KGE8c3ViPmk8XC9zdWI+LCBhPHN1Yj5pKzE8XC9zdWI+KVx1Yjg1YyBcdWJjMTRcdWFmYjhcdWIyOTQgXHVjNWYwXHVjMGIwXHVjNzc0XHViMmU0LiBcdWM3NzQgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YmE3NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDFcdWI5Y2NcdWQwN2MgXHVjNzkxXHVjNTQ0XHVjOWMwXHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0cmVkdWNlXHVjNWYwXHVjMGIwXHVjNzU4IFx1YmU0NFx1YzZhOVx1Yzc0MCBtYXgoYTxzdWI+aTxcL3N1Yj4sIGE8c3ViPmkrMTxcL3N1Yj4pXHVhY2ZjIFx1YWMxOVx1YjJlNC4gXHVjNWYwXHVjMGIwXHVjNzQ0IG4tMVx1YmM4OCBcdWMwYWNcdWM2YTlcdWQ1NThcdWJhNzQsIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMVx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdHJlZHVjZVx1YzVmMFx1YzBiMFx1Yzc0NCBuLTFcdWJjODggXHVjMGFjXHVjNmE5XHVkNTc0XHVjMTFjLCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIDFcdWI4NWMgXHViOWNjXHViNGU0IFx1YjU0YywgXHVjNWYwXHVjMGIwXHVjNzU4IFx1YmU0NFx1YzZhOVx1Yzc1OCBcdWQ1NjlcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0IG4oMSAmbGU7IG4gJmxlOyAxLDAwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWM2ZDBcdWMxOGMgYTxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyBhPHN1Yj5pPFwvc3ViPiAmbGU7IDEsMDAwLDAwMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIDFcdWI4NWMgXHViOWNjXHViNGRjXHViMjk0XHViMzcwIFx1YjRkY1x1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NTggXHVkNTY5XHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzM2NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNlcXVlbmNlIiwiZGVzY3JpcHRpb24iOiI8cD5XZSBhcmUgZ2l2ZW4gYSBzZXF1ZW5jZSBhPHN1Yj4xPFwvc3ViPiwgLi4uLCBhPHN1Yj5uPFwvc3ViPi4gV2UgY2FuIG1hbmlwdWxhdGUgdGhpcyBzZXF1ZW5jZSB1c2luZyB0aGUgb3BlcmF0aW9uIHJlZHVjZShpKSwgd2hpY2ggcmVwbGFjZXMgZWxlbWVudHMgYTxzdWI+aTxcL3N1Yj4gYW5kIGE8c3ViPmkrMTxcL3N1Yj4gd2l0aCBhIHNpbmdsZSBlbGVtZW50IG1heChhPHN1Yj5pPFwvc3ViPiwgYTxzdWI+aSsxPFwvc3ViPiksIHJlc3VsdGluZyBpbiBhIG5ldyBzaG9ydGVyIHNlcXVlbmNlLiBUaGUgY29zdCBvZiB0aGlzIG9wZXJhdGlvbiBpcyBtYXgoYTxzdWI+aTxcL3N1Yj4sIGE8c3ViPmkrMTxcL3N1Yj4pLiBBZnRlciBuICZtaW51czsgMSBvcGVyYXRpb25zIHJlZHVjZSwgd2Ugb2J0YWluIGEgc2VxdWVuY2Ugb2YgbGVuZ3RoIDEuIE91ciB0YXNrIGlzIHRvIGNvbXB1dGUgdGhlIGNvc3Qgb2YgdGhlIG9wdGltYWwgcmVkdWNpbmcgc2NoZW1lLCBpLmUuIHRoZSBzZXF1ZW5jZSBvZiByZWR1Y2Ugb3BlcmF0aW9ucyB3aXRoIG1pbmltYWwgY29zdCBsZWFkaW5nIHRvIGEgc2VxdWVuY2Ugb2YgbGVuZ3RoIDEuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgY29udGFpbnMgbiAoMSAmbGU7IG4gJmxlOyAxLDAwMCwwMDApLCB0aGUgbGVuZ3RoIG9mIHRoZSBzZXF1ZW5jZS4gVGhlIGZvbGxvd2luZyBuIGxpbmVzIGNvbnRhaW4gb25lIGludGVnZXIgYTxzdWI+aTxcL3N1Yj4sIHRoZSBlbGVtZW50cyBvZiB0aGUgc2VxdWVuY2UgKDAgJmxlOyBhPHN1Yj5pPFwvc3ViPiAmbGU7IDEsMDAwLDAwMCwwMDApLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIHRoZSBcdWZiMDFyc3QgYW5kIG9ubHkgbGluZSBvZiB0aGUgb3V0cHV0IHByaW50IHRoZSBtaW5pbWFsIGNvc3Qgb2YgcmVkdWNpbmcgdGhlIHNlcXVlbmNlIHRvIGEgc2luZ2xlIGVsZW1lbnQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d