25ος ΠΔΠ Καμπ (seniors)
Γυμναστής (gymnast)

Ένας γυμναστής ζητάει από τους μαθητές του σχολείου να μπουν σε μια γραμμή σε φθίνουσα σειρά ύψους. Αυτοί όμως μπαίνουν στη σειρά όπως τους έρθει και ο γυμναστής πρέπει να τους τοποθετήσει στη σειρά μόνος του. Κάθε φορά, ο γυμναστής διαλέγει ένα μαθητή και τον μεταφέρει από την θέση \(i\) όπου βρίσκεται σε μια θέση \(j\). Αν \(i > j\), τότε οι θέσεις των μαθητών μεταξύ \(i\) και \(j−1\) αυξάνουν κατά \(1\). Αντίθετα, αν \(i < j\), τότε οι θέσεις των μαθητών μεταξύ \(i+1\) και \(j\) ελαττώνονται κατά \(1\). Ο γυμναστής συνεχίζει να κάνει αυτές τις μετακινήσεις μέχρι κάθε μαθητής να βρεθεί στη σωστή θέση του. Κάθε φορά που κάνει μια μετακίνηση ενός μαθητή από τη θέση \(i\) στη θέση \(j\), ο γυμναστής αναγκάζεται να κάνει \(i+j\) βήματα.

Γράψτε ένα πρόγραμμα να βρίσκει το ελάχιστο συνολικό πλήθος των βημάτων που πρέπει να κάνει ο γυμναστής για να τοποθετήσει όλους τους μαθητές στη σωστή σειρά.

Αρχεία Εισόδου (gymnast.in):

Η είσοδος θα αποτελείται από δύο γραμμές. Η πρώτη γραμμή θα περιέχει ένα φυσικό αριθμό \(N\), το πλήθος των μαθητών. Η δεύτερη γραμμή θα περιέχει \(N\) ακέραιους αριθμούς \(x_1, x_2, \ldots, x_N\), χωρισμένους ανά δύο με ένα κενό διάστημα: το ύψος των μαθητών που βρίσκονται αρχικά στις θέσεις \(1, 2, \ldots, N\), αντίστοιχα. Θεωρήστε ότι δεν υπάρχουν δύο μαθητές με το ίδιο ύψος.

Αρχεία Εξόδου (gymnast.out):

Η έξοδος πρέπει να αποτελείται από μία γραμμή που να περιέχει μόνο έναν φυσικό αριθμό: το ελάχιστο συνολικό πλήθος βημάτων που πρέπει να κάνει ο γυμναστής.

Παραδείγματα Αρχείων Εισόδου - Εξόδου:

1^o

gymnast.in	gymnast.out
5 20 30 5 15 10	11

Εξήγηση 1^ου παραδείγματος: Ο γυμναστής μπορεί να μετακινήσει το μαθητή \(30\) από τη θέση \(2\) στη θέση \(1\) (κόστος \(3\)) και στη συνέχεια τον \(5\) από τη θέση \(3\) στη θέση \(5\) (κόστος \(8\)). Συνολικό κόστος \(3+8=11\). Το κόστος αυτό είναι και το ελάχιστο δυνατό.

2^o

gymnast.in	gymnast.out
10 9 6 2 10 8 7 4 5 1 3	52

Περιορισμοί:

• \(2 \leq N \leq 1.000\).
• \(1 \leq x_i \leq 1.000.000\).
• Όριο χρόνου εκτέλεσης: \(2\) sec.
• Όριο μνήμης: \(64\) MB.