문제
길이가 $N$인 양의 정수로 이루어진 배열 $A = [A_1, A_2, \cdots, A_N]$이 주어집니다. 이 배열을 비내림차순, 즉, $A_1 \le A_2 \le \cdots \le A_N$이 되도록 정렬하기 위해서 다음과 같은 $M$가지 조작을 순서와 횟수에 상관 없이 원하는 만큼 할 수 있습니다.
- $A$의 $l_i$번째 수와 $r_i$번째 수를 바꿉니다. 비용은 $c_i$가 듭니다. $(1 \le i \le M)$
$A$를 비내림차순으로 정렬하기 위해 필요한 비용 총합의 최솟값을 출력하세요.
출력
첫 줄에 배열 $A$를 비내림차순으로 정렬하기 위해 필요한 비용 총합의 최솟값을 출력하세요. 단, 배열을 비내림차순으로 만드는 것이 불가능한 경우 대신 $-1$을 출력하세요.
3,ドル 2, 3$번 조작을 차례대로 사용하면 됩니다.
6,ドル 5$번 조작을 차례대로 사용하면 됩니다.
W3sicHJvYmxlbV9pZCI6IjI4NzA3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViYzMwXHVjNWY0IFx1YzgxNVx1YjgyYyIsImRlc2NyaXB0aW9uIjoiPHA+XHVhZTM4XHVjNzc0XHVhYzAwICROJFx1Yzc3OCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJjMzBcdWM1ZjQgJEEgPSBbQV8xLCBBXzIsIFxcY2RvdHMsIEFfTl0kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gXHVjNzc0IFx1YmMzMFx1YzVmNFx1Yzc0NCBcdWJlNDRcdWIwYjRcdWI5YmNcdWNjMjhcdWMyMWMsIFx1Yzk4OSwgJEFfMSBcXGxlIEFfMiBcXGxlIFxcY2RvdHMgXFxsZSBBX04kXHVjNzc0IFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWM4MTVcdWI4MmNcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgJE0kXHVhYzAwXHVjOWMwIFx1Yzg3MFx1Yzc5MVx1Yzc0NCBcdWMyMWNcdWMxMWNcdWM2NDAgXHVkNjlmXHVjMjE4XHVjNWQwIFx1YzBjMVx1YWQwMCBcdWM1YzZcdWM3NzQgXHVjNmQwXHVkNTU4XHViMjk0IFx1YjljY1x1ZDA3YyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzJiNVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kQSRcdWM3NTggJGxfaSRcdWJjODhcdWM5ZjggXHVjMjE4XHVjNjQwICRyX2kkXHViYzg4XHVjOWY4IFx1YzIxOFx1Yjk3YyBcdWJjMTRcdWFmYzlcdWIyYzhcdWIyZTQuIFx1YmU0NFx1YzZhOVx1Yzc0MCAkY19pJFx1YWMwMCBcdWI0ZWRcdWIyYzhcdWIyZTQuICQoMSBcXGxlIGkgXFxsZSBNKSQ8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4kQSRcdWI5N2MgXHViZTQ0XHViMGI0XHViOWJjXHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1YzgxNVx1YjgyY1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YmU0NFx1YzZhOSBcdWNkMWRcdWQ1NjlcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzEzOFx1YzY5NC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHViYzMwXHVjNWY0ICRBJFx1Yzc1OCBcdWFlMzhcdWM3NzQgJE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gJCgyIFxcbGUgTiBcXGxlIDgpJDxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwICRBJFx1Yzc1OCBcdWFjMDEgXHVjNmQwXHVjMThjICRBXzEsIFxcY2RvdHMsIEFfTiRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuICQoMSBcXGxlIEFfaSBcXGxlIDEwKSQ8XC9wPlxyXG5cclxuPHA+XHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4NzBcdWM3OTFcdWM3NTggXHVhYzFjXHVjMjE4ICRNJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuICQoMSBcXGxlIE0gXFxsZSAxMCkkPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyAkTSRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNzU4ICRpJFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODcwXHVjNzkxXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YjI5NCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCAkbF9pLCByX2ksIGNfaSRcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuICQoMSBcXGxlIGxfaSAmbHQ7IHJfaSBcXGxlIE47JCAkMSBcXGxlIGNfaSBcXGxlIDEwKSQ8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YmMzMFx1YzVmNCAkQSRcdWI5N2MgXHViZTQ0XHViMGI0XHViOWJjXHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1YzgxNVx1YjgyY1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YmU0NFx1YzZhOSBcdWNkMWRcdWQ1NjlcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzEzOFx1YzY5NC4gXHViMmU4LCBcdWJjMzBcdWM1ZjRcdWM3NDQgXHViZTQ0XHViMGI0XHViOWJjXHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWFjODNcdWM3NzQgXHViZDg4XHVhYzAwXHViMmE1XHVkNTVjIFx1YWNiZFx1YzZiMCBcdWIzMDBcdWMyZTAgJC0xJFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWMxMzhcdWM2OTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPiQzLCAyLCAzJFx1YmM4OCBcdWM4NzBcdWM3OTFcdWM3NDQgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YmE3NCBcdWI0MjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPiQ2LCA1JFx1YmM4OCBcdWM4NzBcdWM3OTFcdWM3NDQgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YmE3NCBcdWI0MjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjg3MDciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBcnJheSBTb3J0aW5nIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIGdpdmVuIGFuIGFycmF5ICRBID0gW0FfMSwgQV8yLCBcXGNkb3RzLCBBX05dJCBvZiAkTiQgcG9zaXRpdmUgaW50ZWdlcnMuIFlvdSB3YW50IHRvIHNvcnQgdGhpcyBhcnJheSBpbiBub24tZGVzY2VuZGluZyBvcmRlciwgaS5lLiwgJEFfMSBcXGxlIEFfMiBcXGxlIFxcY2RvdHMgXFxsZSBBX04kLiBUbyBhY2hpZXZlIHRoaXMsIHlvdSBjYW4gcGVyZm9ybSBhbnkgb2YgdGhlIGZvbGxvd2luZyAkTSQgb3BlcmF0aW9ucyBpbiBhbnkgb3JkZXIgYW5kIGFzIG1hbnkgdGltZXMgYXMgeW91IHdhbnQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+U3dhcCB0aGUgJGxfaSQmIzM5O3RoIGFuZCAkcl9pJCYjMzk7dGggbnVtYmVycyBvZiAkQSQuIFRoZSBjb3N0IGlzICRjX2kkLiAkKDEgXFxsZSBpIFxcbGUgTSkkPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+UHJpbnQgdGhlIG1pbmltdW0gdG90YWwgY29zdCByZXF1aXJlZCB0byBzb3J0ICRBJCBpbiBub24tZGVzY2VuZGluZyBvcmRlci48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBsZW5ndGggJE4kIG9mIHRoZSBhcnJheSAkQSQuICQoMiBcXGxlIE4gXFxsZSA4KSQ8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIHRoZSBlbGVtZW50cyAkQV8xLCBcXGNkb3RzLCBBX04kIG9mICRBJCwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuICQoMSBcXGxlIEFfaSBcXGxlIDEwKSQ8XC9wPlxyXG5cclxuPHA+VGhlIHRoaXJkIGxpbmUgY29udGFpbnMgdGhlIG51bWJlciBvZiBvcGVyYXRpb25zICRNJC4gJCgxIFxcbGUgTSBcXGxlIDEwKSQ8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgJE0kIGxpbmVzIGNvbnRhaW4gdGhyZWUgaW50ZWdlcnMgJGxfaSwgcl9pLCBjX2kkIHdoaWNoIHJlcHJlc2VudCBhbiBvcGVyYXRpb24sIHNlcGFyYXRlZCBieSBhIHNwYWNlLiAkKDEgXFxsZSBsX2kgJmx0OyByX2kgXFxsZSBOOyQgJDEgXFxsZSBjX2kgXFxsZSAxMCkkPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgdGhlIG1pbmltdW0gdG90YWwgY29zdCByZXF1aXJlZCB0byBzb3J0ICRBJCBpbiBub24tZGVzY2VuZGluZyBvcmRlciBpbiB0aGUgZmlyc3QgbGluZS4gSWYgaXQgaXMgaW1wb3NzaWJsZSB0byBtYWtlIHRoZSBhcnJheSBub24tZGVzY2VuZGluZywgcHJpbnQgJC0xJCBpbnN0ZWFkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+WW91IGNhbiB1c2Ugb3BlcmF0aW9ucyAkMyQsICQyJCwgYW5kICQzJCBpbiBvcmRlci48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8yIjoiPHA+WW91IGNhbiB1c2Ugb3BlcmF0aW9ucyAkNiQgYW5kICQ1JCBpbiBvcmRlci48XC9wPlxyXG4ifV0=