| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 176 | 119 | 101 | 71.127% |
길이 $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를 출력한다.
가능한 답이 여러 가지이면 그중 하나만 출력한다.
3 2 1 3
YES 1 2
2 1 2
NO