0064. Беспорядок в библиотеке

Имя входного файла: library.in
Имя выходного файла: library.out
Ограничение по времени: 2 s
Ограничение по памяти: 64 megabytes

Небрежные читатели библиотеки часто ставят книги на полки не на свое место. Один из способов измерить беспорядок в библиотеке – посмотреть, какое минимальное количество раз пришлось бы брать книгу на одном месте и переставлять ее на другое.

Перестановку a1, a2, ,…, an операция "удаления-вставки" заменяет на a1, a2, … , ai-1, ai+1, … , aj, ai, aj+1, ,… , an при некотороых i и j (возможны варианты как i<j, так и i>j).

Подсчитать минимальное количество операций удаления-вставки, необходимое для упорядочения заданной перестановки.

Формат входного файла

Первая строка входного файла содержит целое n (1 ≤ n ≤ 10000), следующие несколько – элементы перестановки 1≤ aj≤ n,  j∈1… n, разделенные пробелами и/или переводами строки.

Формат выходного файла

Выходной файл должен содержать искомое значение.

Пример:

input.txtoutput.txt
7 2 4 3 5 1 7 63


Источник: Petrozavodsk Winter 2003. Take-Off, Monday, February 03

Обсудить       Отправить решение



Версия для печати