Занятие 17

Дисковое пространство поделено на так называемые кластеры. При записи на диск файлы разделяются на части размером с кластер. Если все части файла размещены последовательно в последовательных кластерах диска, то последовательное чтение файла происходит максимально быстро. При изменении файла отдельные его части (фрагменты) могут оказаться разбросанными по всему диску в произвольном порядке, т. е. файл становится фрагментированным. При этом быстродействие компьютера снижается. Обычно дефраментация проводится, когда число фрагментированных файлов составляет 10-20% или более от числа всех файлов. Для определения степени фрагментации можно использовать таблицу размещения файлов FAT (File Allocation Table). Упрощенно ее можно описать следующим образом. Дисковое пространство делится на `M` кластеров, нумерующихся с 1 до `M`. В таблице FAT для каждого кластера диска записывается число 0, если соответствующий кластер свободен, или число `-1`, если это последний кластер файла, или число от 1 до `M`, указывающее на следующий кластер, занятый файлом.

Во входном файле в первой строке содержится количество кластеров на диске `M` (`1\ ≤\ M\ ≤\ 500000`), в последующих `M` строках – таблица FAT. Данные корректны, т.е. не содержат циклов и пересечений.

В выходной файл вывести в первой строке вывести общее число файлов на диске, во второй строке – число фрагментированных файлов. Файл будем считать не фрагментированным, если для всех частей файла верно, что `i` часть файла занимает `b+i-1` кластер, где `b` – первый кластер файла.

5
3
0
-1
5
-1

2
1