아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

선생님의 정렬

면접 대비

시간 제한1초메모리 제한512 MB

요약
주어진 배열을 각 위치가 최대 한 번만 사용되는 교환들로 정렬할 수 있는지 판별하고, 가능하면 그 교환 순서를 출력한다.
난이도

보통10점 중 6점

유형
정렬, 그리디, 배열, 해시맵
정답자
아직 제출이 없습니다

문제

9학년 학생들이 체육 시간에 장거리 달리기를 마쳤다. 수업이 거의 끝나가자 선생님은 학생들에게 키가 감소하지 않는 순서로 한 줄로 서라고 했다. 학생들은 항상 집중하지 않기 때문에, 때때로 요청받은 순서대로 서지 않는다. 선생님은 이 문제를 해결하려고 한다.

선생님은 줄을 보고, 제대로 정렬되어 있지 않으면 줄에서 ii번째 학생과 jj번째 학생을 골라 서로 바꾼다. 따라서 교환 후에 ii번째 학생은 jj번째 학생이 되고, 그 반대도 마찬가지다. 선생님은 줄이 제대로 정렬될 때까지, 즉 모든 ii에 대해 (i+1)(i+1)번째 학생이 ii번째 학생보다 키가 작지 않을 때까지 교환을 계속한다.

하지만 오늘은 선생님에게 쉽지 않다. 학생들은 달리기 후에 매우 피곤해서 겨우 서 있을 수 있다. 선생님은 그들에게 신체적으로 부담을 주고 싶지 않아서, 어떤 학생도 한 번 이상 움직이지 않는다.

선생님은 여러분의 도움이 필요하다. 줄 a_1,a_2,…,a_na\_1, a\_2, \ldots, a\_n이 주어진다. 이는 학생들의 키다. 선생님이 줄을 제대로 정렬하기 위한 교환 순서를 찾거나, 불가능하다고 말하여라.

입력

첫째 줄에는 정수 nn이 주어진다. 이는 학생 수다 (1≤n≤2⋅1051 \le n \le 2 \cdot 10^5).

둘째 줄에는 nn개의 정수 a_1,a_2,…,a_na\_1, a\_2, \ldots, a\_n이 주어진다 (0≤a_i≤1090 \le a\_i \le 10^9). a_ia\_i는 줄에서 ii번째 학생의 키다.

출력

선생님이 학생들을 제대로 정렬할 수 없다면 "No"를 출력한다.

그렇지 않으면 첫째 줄에 "Yes"를 출력한다. 둘째 줄에는 선생님이 해야 하는 교환 횟수 kk를 출력한다. 다음 kk개의 줄 각각에는 두 정수 ii와 jj를 출력한다. 이는 선생님이 줄에서 ii번째와 jj번째 학생을 교환해야 함을 나타낸다.

교환 횟수를 최소화할 필요는 없다. 어떤 학생도 한 번 이상 교환되지 않도록 하면서 줄을 제대로 정렬하는 임의의 순서를 출력하면 된다.

예제3

  1. 예제 1

    입력
    3
    3 2 1
    
    예상 출력
    Yes
    1
    3 1
    
  2. 예제 2

    입력
    6
    2 5 5 2 10 9
    
    예상 출력
    Yes
    2
    5 6
    2 4
    
  3. 예제 3

    입력
    5
    2 3 4 5 1
    
    예상 출력
    No