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

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

3 секунди
512 мегабайтів
Складна

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

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

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

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

Вхідні дані

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

У другому рядку задано цілих чисел v_1, v_2, \ldots, v_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.

Вихідні дані

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

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

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

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

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

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

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