Зеник і сортування

Обмеження: 2 сек., 256 МіБ

У Зеника є перестановка \(p\) довжини \(n\). Він хоче її посортувати виконавши якнайменше операцій. За одну операцію Зеник може вибрати будь-які два елементи і поміняти їх місцями. Знайдіть оптимальну послідовність дій, які варто виконати Зенику.

Вхідні дані

У першому рядку задано одне ціле число \(n\) — довжина перестановки.

У другому рядку через пробіл задано \(n\) чисел \(p_i\) — елементи перестановки.

Вихідні дані

У першому рядку виведіть одне ціле число \(k\) — кількість дій щоб відсортувати перестановку.

У наступних \(k\) рядках виведіть по 2 цілі числа \(i\) та \(j\) — які описують, що Зенику потрібно поміняти місями \(i\)-тий та \(j\)-тий елементи.

Обмеження

\(1 \le n \le 10^5\).

В задачі є 5 тестів. Нехай оптимальна кількість операцій \(m\), а кількість операцій вашого розв’язку \(k\).

Якщо \(k = m\) — Ви отримаєте 5 балів за тест,

якщо \(k \le 2 \cdot m\) — Ви отримаєте 4 бали за тест,

якщо \(k \le 3 \cdot m\) — Ви отримаєте 3 бали за тест,

якщо \(k \le 4 \cdot m\) — Ви отримаєте 2 бали за тест,

якщо \(k \le 7 \cdot m\) — Ви отримаєте 1 бал за тест,

якщо \(k > 7 \cdot m\) — Ви отримаєте 0 балів за тест.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 3 5 1 4 2	2 2 5 3 1