Огряче сортування

Обмеження: 3 сек., 512 МіБ

Що станеться, якщо накласти прокляття огра на модуль оперативної пам’яті? Виявляється, вона може циклічно переміщувати довільні послідовності даних ефективним способом, але лише вночі.
Знайдіть мінімальну ціну (та коректну послідовність ходів), необхідну для впорядкування перестановки \(v\) довжини \(n\). Усі елементи перестановки мають індекси від 1 до \(n\).

Єдиний дозволений тип ходу полягає в тому, щоб узяти елемент з деякої позиції \(x\) і вставити його в іншу позицію \(y\), зміщуючи всі елементи між ними на одну позицію. Вартість такого ходу дорівнює \(y\).

Формально, хід бере елемент зі значенням \(t\) із позиції \(x\), звільняючи індекс \(x\). Потім решта елементів у \(v\) зсуваються таким чином, що звільнена позиція стає \(y\). Після цього \(t\) вставляється у звільнену позицію з індексом \(y\).

Наприклад, якщо ми маємо перестановку [4, 3, 2, 1], можливі деякі ходи:

• \(x=2\), \(y=4\), в результаті отримаємо — [4, 2, 1, 3], вартість ходу — 4.

• \(x=2\), \(y=1\), в результаті отримаємо — [3, 4, 2, 1], вартість ходу — 1.

Вхідні дані

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

У другому рядку задано \(n\) цілих чисел \(v_1, v_2, \ldots, v_n\) — перестановку.

Вихідні дані

У першому рядку виведіть два цілих числа \(min\_cost\) та \(len\_moves\) — мінімальну ціну, необхідну щоб впорядкувати перестановку та кількість ходів необхідну для цього.

у наступних \(len\_moves\) рядках виведіть по два цілих числа \(x_k\), \(y_k\). Вони описуватимуть, що на \(k\)-тому ході елемент з позиції \(x_k\) перейде до позиції \(y_k\) (\(1 \leq k \leq len\_moves\), \(1 \le x_k, y_k \le n\)).

Якщо існує декілька можливих послідовностей ходів, ви можете вивести будь-яку з них. Зверніть увагу, що вам не потрібно мінімізувати кількість ходів, лише загальну вартість. Можна показати, що послідовність ходів для впорядкування перестановки існує завжди.

Обмеження

\(1 \leq n \leq 3 \cdot 10^5\),

\(1 \leq v_i \leq n\),

\(v_i \neq v_j\) для всіх \(1 \leq i < j \leq n\).

Приклади

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

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

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

Примітки

• У першому прикладі, одним ходом можна поміняти місцями елементи на позиціях \(3\) та \(4\).

• У другому прикладі, перестановка після першого ходу матиме вигляд \([2, 3, 4, 1, 5]\).

• У третьому прикладі, перестановка вже є посортованою, отже отримальна ціна рівна нулю і не потрібно робити жодного ходу.