34ος ΠΔΠ Καμπ (κοινά)
POLICE (police)

Κατά καιρούς έχουν υπάρξει πολλές κλοπές και άλλα περιστατικά στα πανεπιστήμια, με αποτέλεσμα η κοινωνία να θέλει να αυξήσει την φύλαξη σε αυτούς τους χώρους. Για τον λόγο αυτό, η κυβέρνηση αποφάσισε να ιδρύσει την Πανεπιστημιακή Αστυνομία. Ωστόσο, πολλά μέλη της ακαδημαϊκής κοινότητας, αν και συμφωνούν ότι οι χώροι πρέπει να φυλάσσονται, πιστεύουν ότι η λύση που επέλεξε η κυβέρνηση δεν είναι η πλέον κατάλληλη. Λίγες μέρες πριν την έλευση της αστυνομίας στην Πολυτεχνειούπολη, αναλαμβάνετε τον δύσκολο ρόλο να γεφυρώσετε τις διαφορές των δύο πλευρών. Σας ζητείται να γράψετε έναν αλγόριθμο ο οποίος θα ελαχιστοποιεί την αστυνομική παρουσία στο ΕΜΠ αλλά ταυτόχρονα θα το διατηρεί “ασφαλές”.

Ο περιφερειακός κυκλικός, δρόμος της Πολυτεχνειούπολης έχει \(N\) φυλάκια σε συγκεκριμένες θέσεις, αριθμημένα από το \(1\) έως το \(N\). Λόγω της γεωμετρίας του δρόμου, αν κάποιος αστυνομικός τοποθετηθεί στο \(i\)-οστό φυλάκιο, μπορεί να βλέπει το δικό του και τα \(k_i - 1\) επόμενα φυλάκια κατά την ωρολογιακή φορά.

Καλείστε να υπολογίσετε τον ελάχιστο αριθμό αστυνομικών που πρέπει να τοποθετηθούν σε φυλάκια έτσι ώστε όλα τα φυλάκια να επιβλέπονται από κάποιον αστυνομικό.

Δεδομένα εισόδου (police.in)

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

Δεδομένα εξόδου (police.out)

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

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

1^o

police.in	police.out
3 2 1 3	1

Εξήγηση παραδείγματος: Από το φυλάκιο \(3\), ένας αστυνομικός μπορεί να δει όλα τα φυλάκια.

2^o

police.in	police.out
4 1 1 1 2	3

Εξήγηση παραδείγματος: Τοποθετούμε έναν αστυνομικό στο φυλάκιο \(2\) και έναν στο φυλάκιο \(3\) καθένας από τους οποίους μπορεί να βλέπει μόνο το δικό του φυλάκιο. Τέλος, τοποθετούμε έναν αστυνομικό στο φυλάκιο \(4\) ο οποίος θα επιβλέπει τα φυλάκια \(4\) και \(1\).

3^o

police.in	police.out
8 1 5 1 4 3 2 1 5	2

Περιορισμοί

\(1 \leq N \leq 1.000.000\),
\(1 \leq k_i \leq N\).

Subtasks

Για περιπτώσεις ελέγχου συνολικής αξίας 10%, θα είναι \(1 \leq N \leq 15\).
Για περιπτώσεις ελέγχου συνολικής αξίας 20%, θα είναι \(1 \leq N \leq 2.000\) και \(1 \leq k_i \leq 50\).
Για περιπτώσεις ελέγχου συνολικής αξίας 20%, θα είναι \(1 \leq N \leq 5.000\).