Seating - Easy
Дизайн и Анализ на Алгоритми, 2011
Time Limit: 0.1s, Memory Limit: 64MiB
Ели и нейните приятели отидоха на кино. Те седнаха на N последователни седалки на един и същи ред, но, както често се случва, скоро след това осъзнаха, че някои от хората не са седнали на седалките, които искат.

Нека номерираме седалките с числата от 1 до N, а претенциите на хората с пермутация на числата от 1 до N. Така всеки човек иска да седне точно на една определена седалка, и всяка седалка е желана точно от един човек. Възможно е, обаче, в началния момент не всеки да седи на седалката, на която иска.

Тъй като редовете в киното са тесни, Ели и нейните приятели могат да се разменят само със съседа си по седалка (тоест или с човека отляво, или с човека отдясно). Те могат да правят много такива размени, докато всеки седне където иска. Помогнете на Ели да определи какъв е минималният брой такива размени, които трябва да се направят, за се наредят приятелите в желания от тях ред.
Вход
На първия ред на стандартния вход ще бъде зададено едно единствено цяло число N – броят хора, които трябва да бъдат настанени на седалките. На втория ред ще бъде зададена пермутация на числата от 1 до N – като първото число указва на коя седалка иска да седи човекът, седнал на първата, второто – на коя седалка иска да седи човекът, седнал на втората и т.н.
Изход
На единствен ред на стандартния изход изведете по едно цяло число – броя размествания на съседни хора, които трябва да се направят, за да се подредят по желания от тях начин.
Ограничения
  • 1 ≤ N ≤ 1,000
Примерен Вход Примерен Изход
3 3 1 2 2
5 1 2 3 4 5 0
10 7 2 6 4 5 1 10 9 3 8 20
В първия пример трябва да се разменят 3 с 1 и после 3 с 2, като след тези размени са в реда 1, 2, 3. Във втория тест всеки вече си е на мястото, следователно броят размени е нула.
Мрън!