Analyse von Permutationen unter Berücksichtigung von Inversionen und Brüchen

Python Hard lists

Aufgabe «Analyse von Permutationen unter Berücksichtigung von Inversionen und Brüchen»

Gegeben ist eine Permutation der Zahlen von 1 bis n. Es soll bestimmt werden, ob sie „nahezu identisch“ ist: Die Anzahl der Inversionen (Paare i<j, wobei a[i] > a[j]) muss dem maximal möglichen Wert für Permutationen mit einer festgelegten Anzahl von Brüchen entsprechen. Ein Bruch ist eine Position k, an der a[k] != k. Wenn die Permutation die Bedingung erfüllt, geben Sie die Anzahl der Brüche aus, andernfalls geben Sie -1 aus. Zusätzlich: Wenn die Anzahl der Brüche gleich 0 ist, geben Sie 0 aus. Wenn die Permutation unmöglich ist (z. B. ungültige Daten), geben Sie -2 aus.

Eingabeformat

In der ersten Zeile eine ganze Zahl n (1 ≤ n ≤ 10^5). In der zweiten Zeile n ganze Zahlen — die Permutation.

Ausgabeformat

Eine ganze Zahl: die Anzahl der Brüche, -1 oder -2.

Beispiele

Beispiel 1

EINGABE

abacaba
abacaba

AUSGABE

7

Beispiel 2

EINGABE

3
3 2 1

AUSGABE

-1

main.py