시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB17611910171.127%

문제

  • 길이 $N$의 순열(permutation)이란, $1$부터 $N$까지의 수가 각각 한 번씩 등장하는 수열을 의미한다.
  • 증가하는 수열(increasing sequence)이란, 각 원소가 그 앞의 원소보다 큰 수열을 의미한다.
  • 어떤 수열의 부분 수열(subsequence)이란, 원래 수열에서 몇 개의 원소를 제거하여 얻을 수 있는 수열을 의미한다. 예를 들어, 수열 $[1,3,5]$의 부분 수열로 가능한 것을 모두 나열하면 $[]$, $[1]$, $[3]$, $[5]$, $[1,3]$, $[3,5]$, $[1,5]$, $[1,3,5]$와 같다.
  • 어떤 수열의 최장 증가 부분 수열(longest increasing subsequence, LIS)이란, 증가하는 부분 수열 중 길이가 최대인 것을 의미한다. 예를 들어, 수열 $[4,1,3,5,2,6]$의 LIS로는 $[1,3,5,6]$이 있으며 길이는 $4$이다.

길이 $N$의 순열 $A$가 주어진다. 이 순열에서 서로 다른 두 위치의 원소를 정확히 한 번 교환하려 한다.

교환 이후의 순열에서 최장 증가 부분 수열(LIS)의 길이가 기존 순열의 LIS의 길이보다 감소하지 않도록 할 수 있는지 판별하고, 가능하다면 그러한 두 원소의 위치를 하나 출력하여라.

입력

첫째 줄에 정수 $N$이 주어진다. ($2\le N\le 1\, 000\, 000$)

둘째 줄에 서로 다른 $N$개의 정수 $A_1,A_2,\cdots ,A_N$이 공백으로 구분되어 주어진다. ($1\le A_i\le N$)

출력

두 원소를 정확히 한 번 교환하여 LIS의 길이가 감소하지 않도록 만들 수 있다면 첫째 줄에 YES를 출력한다. 이 경우 둘째 줄에 교환할 두 원소의 인덱스 $i$, $j$를 공백으로 구분하여 오름차순으로 출력한다. ($1\le i<j\le N$)

그러한 교환이 존재하지 않으면 첫째 줄에 NO를 출력한다.

가능한 답이 여러 가지이면 그중 하나만 출력한다.

예제 입력 1

3
2 1 3

예제 출력 1

YES
1 2

예제 입력 2

2
1 2

예제 출력 2

NO
W3sicHJvYmxlbV9pZCI6IjM1NDY3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiU3dhcC1MSVMiLCJkZXNjcmlwdGlvbiI6Ijx1bD5cclxuPGxpPlx1YWUzOFx1Yzc3NCAkTiRcdWM3NTggPHN0cm9uZz5cdWMyMWNcdWM1ZjQocGVybXV0YXRpb24pPFwvc3Ryb25nPlx1Yzc3NFx1Yjc4MCwgJDEkXHViZDgwXHVkMTMwICROJFx1YWU0Y1x1YzljMFx1Yzc1OCBcdWMyMThcdWFjMDAgXHVhYzAxXHVhYzAxIFx1ZDU1YyBcdWJjODhcdWM1MjkgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxsaT48c3Ryb25nPlx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWMyMThcdWM1ZjQoaW5jcmVhc2luZyBzZXF1ZW5jZSk8XC9zdHJvbmc+XHVjNzc0XHViNzgwLCBcdWFjMDEgXHVjNmQwXHVjMThjXHVhYzAwIFx1YWRmOCBcdWM1NWVcdWM3NTggXHVjNmQwXHVjMThjXHViY2Y0XHViMmU0IFx1ZDA3MCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL2xpPlxyXG48bGk+XHVjNWI0XHViNWE0IFx1YzIxOFx1YzVmNFx1Yzc1OCA8c3Ryb25nPlx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjQoc3Vic2VxdWVuY2UpPFwvc3Ryb25nPlx1Yzc3NFx1Yjc4MCwgXHVjNmQwXHViNzk4IFx1YzIxOFx1YzVmNFx1YzVkMFx1YzExYyBcdWJhODcgXHVhYzFjXHVjNzU4IFx1YzZkMFx1YzE4Y1x1Yjk3YyBcdWM4MWNcdWFjNzBcdWQ1NThcdWM1ZWMgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjMjE4XHVjNWY0ICRbMSwzLDVdJFx1Yzc1OCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHViODVjIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjODNcdWM3NDQgXHViYWE4XHViNDUwIFx1YjA5OFx1YzVmNFx1ZDU1OFx1YmE3NCAkW10kLCAkWzFdJCwgJFszXSQsICRbNV0kLCAkWzEsM10kLCAkWzMsNV0kLCAkWzEsNV0kLCAkWzEsMyw1XSRcdWM2NDAgXHVhYzE5XHViMmU0LjxcL2xpPlxyXG48bGk+XHVjNWI0XHViNWE0IFx1YzIxOFx1YzVmNFx1Yzc1OCA8c3Ryb25nPlx1Y2Q1Y1x1YzdhNSBcdWM5OWRcdWFjMDAgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNChsb25nZXN0IGluY3JlYXNpbmcgc3Vic2VxdWVuY2UsIExJUyk8XC9zdHJvbmc+XHVjNzc0XHViNzgwLCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNCBcdWM5MTEgXHVhZTM4XHVjNzc0XHVhYzAwIFx1Y2Q1Y1x1YjMwMFx1Yzc3OCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWMyMThcdWM1ZjQgJFs0LDEsMyw1LDIsNl0kXHVjNzU4IExJU1x1Yjg1Y1x1YjI5NCAkWzEsMyw1LDZdJFx1Yzc3NCBcdWM3ODhcdWM3M2NcdWJhNzAgXHVhZTM4XHVjNzc0XHViMjk0ICQ0JFx1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWFlMzhcdWM3NzQgJE4kXHVjNzU4IFx1YzIxY1x1YzVmNCAkQSRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjMjFjXHVjNWY0XHVjNWQwXHVjMTFjIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViNDUwIFx1YzcwNFx1Y2U1OFx1Yzc1OCBcdWM2ZDBcdWMxOGNcdWI5N2MgXHVjODE1XHVkNjU1XHVkNzg4IFx1ZDU1YyBcdWJjODggXHVhZDUwXHVkNjU4XHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZDUwXHVkNjU4IFx1Yzc3NFx1ZDZjNFx1Yzc1OCBcdWMyMWNcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVjZDVjXHVjN2E1IFx1Yzk5ZFx1YWMwMCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0KExJUylcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIFx1YWUzMFx1Yzg3NCBcdWMyMWNcdWM1ZjRcdWM3NTggTElTXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YmNmNFx1YjJlNCA8c3Ryb25nPlx1YWMxMFx1YzE4Y1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIzYzRcdWI4NWQgPFwvc3Ryb25nPlx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1ZDMxMFx1YmNjNFx1ZDU1OFx1YWNlMCwgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0XHViYTc0IFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWI0NTAgXHVjNmQwXHVjMThjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWQ1NThcdWIwOTggXHVjZDljXHViODI1XHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMTggJE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKCQyXFxsZSBOXFxsZSAxXFwsIDAwMFxcLCAwMDAkKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggJE4kXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCAkQV8xLEFfMixcXGNkb3RzICxBX04kXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoJDFcXGxlIEFfaVxcbGUgTiQpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViNDUwIFx1YzZkMFx1YzE4Y1x1Yjk3YyBcdWM4MTVcdWQ2NTVcdWQ3ODggXHVkNTVjIFx1YmM4OCBcdWFkNTBcdWQ2NThcdWQ1NThcdWM1ZWMgTElTXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWFjMTBcdWMxOGNcdWQ1NThcdWM5YzAgXHVjNTRhXHViM2M0XHViODVkIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0XHViYTc0IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPllFUzxcL2NvZGU+PFwvc3Bhbj5cdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhY2JkXHVjNmIwIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhZDUwXHVkNjU4XHVkNTYwIFx1YjQ1MCBcdWM2ZDBcdWMxOGNcdWM3NTggXHVjNzc4XHViMzcxXHVjMmE0ICRpJCwgJGokXHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjNjI0XHViOTg0XHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gKCQxXFxsZSBpJmx0O2pcXGxlIE4kKTxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI3ZWNcdWQ1NWMgXHVhZDUwXHVkNjU4XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQgXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+Tk88XC9jb2RlPjxcL3NwYW4+XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAwXHViMmE1XHVkNTVjIFx1YjJmNVx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVjNzc0XHViYTc0IFx1YWRmOFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5Y2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjM1NDY3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3dhcC1MSVMiLCJkZXNjcmlwdGlvbiI6Ijx1bD5cclxuXHQ8bGk+QSA8c3Ryb25nPnBlcm11dGF0aW9uPFwvc3Ryb25nPiBvZiBsZW5ndGggJE4kIGlzIGEgc2VxdWVuY2UgaW4gd2hpY2ggZWFjaCBpbnRlZ2VyIGZyb20gJDEkIHRvICROJCBhcHBlYXJzIGV4YWN0bHkgb25jZS48XC9saT5cclxuXHQ8bGk+QW4gPHN0cm9uZz5pbmNyZWFzaW5nIHNlcXVlbmNlPFwvc3Ryb25nPiBpcyBhIHNlcXVlbmNlIGluIHdoaWNoIGVhY2ggZWxlbWVudCBpcyBncmVhdGVyIHRoYW4gdGhlIHByZXZpb3VzIG9uZS48XC9saT5cclxuXHQ8bGk+QSA8c3Ryb25nPnN1YnNlcXVlbmNlPFwvc3Ryb25nPiBvZiBhIHNlcXVlbmNlIGlzIGEgc2VxdWVuY2Ugb2J0YWluZWQgYnkgcmVtb3Zpbmcgc29tZSBlbGVtZW50cyBmcm9tIHRoZSBvcmlnaW5hbCBzZXF1ZW5jZS4gRm9yIGV4YW1wbGUsIGFsbCBwb3NzaWJsZSBzdWJzZXF1ZW5jZXMgb2YgJFsxLDMsNV0kIGFyZSAkW10kLCAkWzFdJCwgJFszXSQsICRbNV0kLCAkWzEsM10kLCAkWzMsNV0kLCAkWzEsNV0kLCBhbmQgJFsxLDMsNV0kLjxcL2xpPlxyXG5cdDxsaT5BIDxzdHJvbmc+bG9uZ2VzdCBpbmNyZWFzaW5nIHN1YnNlcXVlbmNlIChMSVMpPFwvc3Ryb25nPiBvZiBhIHNlcXVlbmNlIGlzIGFuIGluY3JlYXNpbmcgc3Vic2VxdWVuY2Ugd2l0aCB0aGUgbWF4aW11bSBwb3NzaWJsZSBsZW5ndGguIEZvciBleGFtcGxlLCBhbiBMSVMgb2YgJFs0LDEsMyw1LDIsNl0kIGlzICRbMSwzLDUsNl0kLCBhbmQgaXRzIGxlbmd0aCBpcyAkNCQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+WW91IGFyZSBnaXZlbiBhIHBlcm11dGF0aW9uICRBJCBvZiBsZW5ndGggJE4kLiBZb3Ugd2FudCB0byBzd2FwIHRoZSBlbGVtZW50cyBhdCB0d28gZGlzdGluY3QgcG9zaXRpb25zIGV4YWN0bHkgb25jZS48XC9wPlxyXG5cclxuPHA+RGV0ZXJtaW5lIHdoZXRoZXIgaXQgaXMgcG9zc2libGUgdG8gc3dhcCB0d28gZWxlbWVudHMgc28gdGhhdCB0aGUgbGVuZ3RoIG9mIHRoZSBsb25nZXN0IGluY3JlYXNpbmcgc3Vic2VxdWVuY2UgKExJUykgPHN0cm9uZz5kb2VzIG5vdCBkZWNyZWFzZTxcL3N0cm9uZz4uIElmIGl0IGlzIHBvc3NpYmxlLCBvdXRwdXQgb25lIHN1Y2ggcGFpciBvZiBwb3NpdGlvbnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyICROJC4gKCQyXFxsZSBOXFxsZSAxXFwsIDAwMFxcLCAwMDAkKTxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgJE4kIGRpc3RpbmN0IGludGVnZXJzICRBXzEsQV8yLFxcY2RvdHMgLEFfTiQsIHNlcGFyYXRlZCBieSBzcGFjZXMuICgkMVxcbGUgQV9pXFxsZSBOJCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JZiBpdCBpcyBwb3NzaWJsZSB0byBzd2FwIHR3byBlbGVtZW50cyBleGFjdGx5IG9uY2Ugc28gdGhhdCB0aGUgTElTIGxlbmd0aCBkb2VzIG5vdCBkZWNyZWFzZSwgcHJpbnQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPllFUzxcL2NvZGU+PFwvc3Bhbj4gb24gdGhlIGZpcnN0IGxpbmUuIEluIHRoaXMgY2FzZSwgcHJpbnQgdGhlIGluZGljZXMgJGkkIGFuZCAkaiQgb2YgdGhlIHR3byBlbGVtZW50cyB0byBzd2FwIG9uIHRoZSBzZWNvbmQgbGluZSwgaW4gaW5jcmVhc2luZyBvcmRlciBhbmQgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuICgkMVxcbGUgaSZsdDtqXFxsZSBOJCk8XC9wPlxyXG5cclxuPHA+SWYgbm8gc3VjaCBzd2FwIGV4aXN0cywgcHJpbnQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPk5PPFwvY29kZT48XC9zcGFuPiBvbiB0aGUgZmlyc3QgbGluZS48XC9wPlxyXG5cclxuPHA+SWYgdGhlcmUgYXJlIG11bHRpcGxlIHBvc3NpYmxlIGFuc3dlcnMsIHByaW50IGFueSBvbmUgb2YgdGhlbS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d