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

Input file name:	library.in
Output file name:	library.out
Time limit:	2 s
Memory limit:	64 megabytes

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

Перестановку a₁, a₂, ,…, a_n операция "удаления-вставки" заменяет на a₁, a₂, … , a_i-1, a_i+1, … , a_j, a_i, a_j+1, ,… , a_n при некотороых i и j (возможны варианты как i<j, так и i>j).

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

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

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

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

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

Пример:

input.txt	output.txt
7 2 4 3 5 1 7 6	3

Source: Petrozavodsk Winter 2003. Take-Off, Monday, February 03

Discuss       Submit a solution



Printable version