QSwap

Time limit: 1s
Memory limit: 256MB
Input:
Output:

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)swap(i, i + 1), 1 ≤ i < N și maxim o dată operația oferită de Radu, swap(i,j)swap(i, j), 1 ≤ i < j ≤ N, unde rezultatul operației swap(x,y)swap(x, y) aplicate asupra permutării p=p1,p2,...,px,...,py,...,pNp = p_1, p_2, ... , p_x, ... , p_y, ..., p_N este p=p1,p2,...,py,...,px,...,pNp' = 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 p1...pNp_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).

Problem info

ID: 94

Editor: liviu

Source: Lot 2021 Baraj 2 Seniori: Problema 1

Tags:

Lot 2021 Baraj 2 Seniori

Log in or sign up to be able to send submissions!