Задача A. НЖМД Имя входного файла: harddrive.in
Имя выходного файла: harddrive.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Бедному НЖМД уже много лет. И все эти годы он непрестанно трудится в недрах старого ПК.
НЖМД — это ни что иное как обычный жесткий диск на котором хранится один большой Очень
Важный Файл. И НЖМД очень устал непрестанно крутиться, чтобы обеспечивать постоянный
доступ к этому Файлу.
Как известно, для хранения файлы разбиваются на много блоков одинакового размера, которые
могут хранится в различных местах жесткого диска, не обязательно последовательно — это
называется фрагментацией. Вот и сейчас получилось, что Очень Важный Файл занимает весь
НЖМД, но блоки, на которые он разбит, расположены не последовательно.
Данные с жесткого диска могут считываться специальной считывающей головкой, причем
для доступа к различным местам жесткого диска считывающая головка вращается относительно
жесткого диска, но всегда в одну и ту же сторону. Блоки можно считывать только в той
последовательности, в которой они образуют файл, то есть сначала необходимо переместить
головку на место расположения первого блока, считать его, далее переместить головку на место
расположения второго блока, считать его и так далее. Таким образом, из-за непоследовательности
расположения данных получается, что за один оборот жесткого диска, возможно, не получится
считать весь файл.
Вам известно в каком порядке на НЖМД расположены блоки, на которые разбит файл. Ваша
задача состоит в том, чтобы найти минимальное число полных оборотов считывающей головки
относительно жесткого диска, которые ей придется сделать, чтобы прочитать весь файл от первого
до последнего блока.
Формат входного файла
Первая строка входного файла содержит единственное натуральное число n (1 ≤ n ≤ 105
) —
количество блоков, на которые разбит файл.
Следующая строка содержит n различных натуральных чисел pi (1 ≤ pi ≤ n) — перестановку
чисел от 1 до n, задающую в какой последовательности хранятся блоки файла. pi — номер блока,
который хранится на i-ом месте в сторону вращения жесткого диска.
Изначально считается, что считывающая головка находится перед первым блоком. Считается,
что головка делает полный оборот, когда ей приходится проходить между n-ым и первым блоком.
Формат выходного файла
В выходной файл выведите единственное целое число — минимальное количество оборотов,
которое необходимо совершить считывающей головке, чтобы прочитать весь Очень Важный Файл
от первого до последнего блока.
Примеры
harddrive.in harddrive.out
3
3 1 2
1
2
1 2
0
4
4 3 2 1
3
нужно решить на паскале

Sofiagatsenko    3   26.10.2020 22:38    5