22ος ΠΔΠ Καμπ (κοινά)
Ενισχυτές (amplifiers)

Έχετε μια ακολουθία \(N\) φυσικών αριθμών (\(1 \leq N \leq 200.000\)), \(A_i (1 \leq i \leq N, 1 \leq A_i \leq 10^9)\).

Σε μία συνεχόμενη υποπεριοχή των αριθμών, ας πούμε από \(L\) μέχρι \(R\) (όπου \(1 \leq L \leq R \leq N\)), μπορείτε να εφαρμόσετε έναν ενισχυτή. Ο ενισχυτής αυξάνει κατά ένα όλους τους αριθμούς \(A_i\) που είναι στην περιοχή (\(L \leq i \leq R\)), αλλά μπορεί να χρησιμοποιηθεί ΜΟΝΟ αν όλοι αυτοί οι αριθμοί είναι ίσοι.

Πρόβλημα

Γράψτε ένα πρόγραμμα που να υπολογίζει το ελάχιστο πλήθος ενισχυτών που πρέπει να εφαρμόσετε (τον έναν μετά τον άλλον) για να κάνετε ίσους όλους τους αριθμούς της ακολουθίας.

Προσέξτε γιατί το πλήθος των ενισχυτών μπορεί να είναι πολύ μεγάλο…

Αρχείο εισόδου

Η πρώτη γραμμή της εισόδου περιέχει τον ακέραιο \(N\). Η δεύτερη γραμμή περιέχει τους \(N\) ακέραιους αριθμούς \(A_i\), χωρισμένους με κενά διαστήματα.

Αρχείο εξόδου

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

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

1^o

amplifiers.in	amplifiers.out
3 1 3 2	3

2^o

amplifiers.in	amplifiers.out
4 1 2 4 2	5

3^o

amplifiers.in	amplifiers.out
5 3 1 4 1 1	6

Περιορισμοί