Teacher Sorting

Interview

Time limit1sMemory limit512 MB

Summary

Given an array, decide whether it can be sorted by disjoint swaps (each index used at most once) and output such a swap sequence.

Level: Medium6 of 10
Topics: Sorting, Greedy, Array, Hash map
Solved: No attempts yet

Problem

The 9th grade students are in Physical Education class, and they have just finished a long-distance run. The lesson is nearing its end, so the teacher asked the students to stand in a line in non-decreasing order of their heights. Students do not always pay attention, so sometimes they stand in a line in an order different from what they were asked. The teacher wants to fix the problem.

The teacher looks at the line, and if it is not ordered properly, chooses the $i$ -th and the $j$ -th student in the line, and swaps them. After the swap, the $i$ -th student becomes the $j$ -th student, and the other way around. The teacher keeps doing swaps until the line is ordered properly. Formally speaking, until for all $i$ the $(i+1)$ -th student is not shorter than the $i$ -th student in the line.

However, today it will not be easy for the teacher. The students are very tired after the run, so they can hardly stand. The teacher does not want to overload them physically, so the teacher will not move any student more than once.

The teacher needs your help. You are given the line: $a\_1, a\_2, \ldots, a\_n$ --- the heights of the students. Find the sequence of swaps for the teacher to make the line ordered properly, or say that it is not possible.

Input

The first line contains an integer $n$ --- the number of students ( $1 \le n \le 2 \cdot 10^5$ ).

The second line contains $n$ integers $a\_1, a\_2, \ldots, a\_n$ ( $0 \le a\_i \le 10^9$ ). The number $a\_i$ is the height of the $i$ -th student in the line.

Output

If the teacher will not be able to order the students properly, print "No".

Otherwise, print "Yes" in the first line. In the second line print an integer $k$ --- the number of swaps the teacher needs to make. In each of the next $k$ lines print two integers $i$ and $j$ , denoting that the teacher should swap the $i$ -th and the $j$ -th students in the line.

You do not have to minimize the number of swaps. You can print any sequence that will make the line ordered properly in a way that no student was swapped more than once.

Examples3

Example 1
Input
```
3
3 2 1
```
Expected output
```
Yes
1
3 1
```
Example 2
Input
```
6
2 5 5 2 10 9
```
Expected output
```
Yes
2
5 6
2 4
```
Example 3
Input
```
5
2 3 4 5 1
```
Expected output
```
No
```