Selecție CPPI 2024 - Mirror Juniori | Mere

This was the problem page during the contest. Access the current page here.
Time limit: 0.2s Memory limit: 64MB Input: mere.in Output: mere.out

Cerință

Într-un sat zin zona de deal cele nn 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 11 la nn. Î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 ii în gospodăria ee este egal cu distanța dintre cele două, adică eie-i.

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

Date de intrare

Fișierul mere.in conține pe prima linie numărul nn iar pe linia a doua, separate prin spații, nn numere naturale ce reprezintă sortimentele de mere produse respectiv în fiecare dintre gospodăriile 1,2,,n1, 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

  • 1n200 0001 \leq n \leq 200 \ 000;
  • Sortimentele de mere sunt valori naturale de cel mult 99 cifre;
  • Pentru 5353 de puncte sortimentele de mere sunt numerotate cu numere consecutive începând cu 11.

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 88, costul ducerii merelor este:

  • 00 pentru sortimentul 11;
  • 11 pentru sortimentul 44;
  • 33 pentru sortimentul 33.

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