Problem QSwap


După ce te-ai jucat cu IP-urile de Neuralink, ai căpătat o pasiune pentru permutări. Ai reușit să faci rost de o permutare p de lungime N și ți-ai propus un obiectiv simplu: să o sortezi efectuând un număr minim de swapuri (interschimbări) între elemente adiacente. Prietenul tău Radu Slav a observat noua ta preocupare, și pentru a te ajuta să nu pierzi prea mult timp sortând permutarea, s-a oferit să te ajute: el îți oferă o extra operație swap specială, pe care o poți folosi la orice moment sau o poți ignora, dar care poate fi efectuată între oricare 2 elemente din p (nu neapărat adiacente). Acum, vrei să calculezi numărul total minim de operații, având în vedere că poți folosi de oricâte ori operația \(swap(i, i + 1)\), 1 ≤ i < N și maxim o dată operația oferită de Radu, \(swap(i, j)\), 1 ≤ i < j ≤ N, unde rezultatul operației \(swap(x, y)\) aplicate asupra permutării \(p = p_1, p_2, ... , p_x, ... , p_y, ..., p_N\) este \(p' = p_1, p_2, ... , p_y, ... , p_x, ..., p_N\) .

Date de intrare

Pe prima linie se găsește un număr întreg N, reprezentând lungimea permutării.
Pe cea de-a doua linie se găsesc N numere întregi \(p_1 ... p_N\) , reprezentând permutarea ce trebuie sortată

Date de ieșire

Se va afișa o singură linie, ce conține un singur număr întreg, reprezentând numărul minim de operații necesare pentru a sorta permutarea.

Restricții și precizări

  • 1 ≤ N ≤ 1 000 000
  • p este o permutare validă numerelor de la 1 la N

Subtask 1 (7 puncte)

  • 1 ≤ N ≤ 10

Subtask 2 (8 puncte)

  • 1 ≤ N ≤ 100

Subtask 3 (9 puncte)

  • 1 ≤ N ≤ 500

Subtask 4 (10 puncte)

  • 1 ≤ N ≤ 2 500

Subtask 5 (11 puncte)

  • 1 ≤ N ≤ 10 000

Subtask 6 (16 puncte)

  • 1 ≤ N ≤ 100 000
  • Permutarea este generată aleator uniform din mulțimea permutărilor de lungime N

Subtask 7 (27 puncte)

  • 1 ≤ N ≤ 250 000

Subtask 8 (12 puncte)

  • Fără restricții suplimentare.

Exemplu

stdin

5
4 2 1 5 3

stdout

3

stdin

10
1 9 6 10 4 2 8 5 7 3

stdout

14

Explicații

Pe primul exemplu swapurile necesare pentru a sorta permutarea sunt (ca poziții): (4, 5), (1, 3), (3, 4), unde operația de interschimbare specială (care nu este între 2 poziții adiacente) este (1, 3).

General info

ID: 94

Upload: liviu

Input: Console Input

Memory limit: 128MB/128MB

Time limit: 1s

Source: Lot 2021 Baraj 2 Seniori: Problema 1

Submissions

Special Submissions