Selecție CPPI 2024 - Mirror Juniori | Mere

Cerință

Într-un sat zin zona de deal cele $n$ gospodării sunt așezate una lângă alta, de-a lungul drumului, toate pe aceeași parte. Acestea sunt numerotate începând de la intrarea în sat, în ordine, cu numere de la $1$ la $n$. În fiecare gospodărie se produce un singur sortiment de mere. Pot fi mai multe gospodării care să aibă același sortiment de mere.

Cu ocazia sărbătoririi zile satului se dorește ca în una dintre case să se organizeze o expoziție în care să se aducă mere din toate sortimentele existente în sat.

Pentru un anume sortiment este suficient să se aducă mere dintr-o singură gospodărie dintre cele care produc.

Mai este o condiție: în gospodăria în care se va organiza expoziția trebuie aduse mere doar din gospodării cu număr de ordine mai mic.

Costul aducerii merelor din gospodăria $i$ în gospodăria $e$ este egal cu distanța dintre cele două, adică $e-i$.

Să se determine costul minim pentru organizarea expoziției.

Date de intrare

Fișierul mere.in conține pe prima linie numărul $n$ iar pe linia a doua, separate prin spații, $n$ numere naturale ce reprezintă sortimentele de mere produse respectiv în fiecare dintre gospodăriile $1, 2, \dots, n$.

Date de ieșire

Fișierul mere.out conține pe prima linie un număr ce reprezintă valoarea cerută.

Restricții și precizări

• $1 \leq n \leq 200 \ 000$;
• Sortimentele de mere sunt valori naturale de cel mult $9$ cifre;
• Pentru $53$ de puncte sortimentele de mere sunt numerotate cu numere consecutive începând cu $1$.

Exemplu

mere.in

9
1 1 3 3 3 4 4 1 1

mere.out

4

Explicație

Dacă organizăm expoziția în gospodăria $8$, costul ducerii merelor este:

• $0$ pentru sortimentul $1$;
• $1$ pentru sortimentul $4$;
• $3$ pentru sortimentul $3$.