Οι φούρνοι του Τάκη

Άλλη μία μέρα σκληρής δουλειάς έφτασε στο τέλος της και ήρθε η ώρα η πιτσαρία να κλείσει. Υπάρχει όμως ένα πρόβλημα! Σήμερα ο βοηθός του Τάκη πήρε ρεπό και ο Τάκης δεν ξέρει πώς να κλείνει τους φούρνους του μόνος του.

Συγκεκριμένα, στην πιτσαρία υπάρχουν ~N~ φούρνοι, αριθμημένοι από ~1~ έως ~N~, και αντίστοιχα ~N~ διακόπτες. Ορισμένοι από τους φούρνους είναι αρχικά αναμμένοι, ενώ οι υπόλοιποι είναι αρχικά σβηστοί. Δηλώνουμε με ~a_i~ την αρχική κατάσταση του ~i~-οστού φούρνου: ~a_i=1~ αν είναι αναμμένος και ~a_i=0~ αν είναι σβηστός.

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

Ο Τάκης πρέπει να σβήσει όλους τους φούρνους, αλλά επειδή βιάζεται θέλει να το κάνει όσο πιο σύντομα γίνεται. Ποιο είναι το ελάχιστο δυνατό πλήθος από διακόπτες που χρειάζεται να χρησιμοποιήσει για να το πετύχει;

Πρόβλημα

Να γράψετε ένα πρόγραμμα σε μία από τις γλώσσες του ΠΔΠ (PASCAL, C, C++, JAVA) το οποίο θα διαβάζει τα δεδομένα εισόδου από το αρχείο oven.in και θα εκτυπώνει τα αποτελέσματα στο αρχείο oven.out.

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

Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό ~N~: το πλήθος των φούρνων και των διακοπτών της πιτσαρίας. Η δεύτερη γραμμή περιέχει ~N~ ακέραιους αριθμούς ~a_1~, ~a_2~, ~...~, ~a_N~​: την αρχική κατάσταση των φούρνων, όπου το ~1~ συμβολίζει αναμμένο φούρνο και το ~0~ συμβολίζει σβηστό φούρνο. Η τρίτη γραμμή περιέχει ~N~ ακέραιους αριθμούς ~k_1~, ~k_2~, ~...~, ~k_N~​: τους χαρακτηριστικούς αριθμούς των διακοπτών.

Αρχεία εξόδου (ovens.out)

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

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

Είσοδος:

6
1 0 0 1 1 0
3 2 3 1 1 0

Έξοδος:

3

Εξήγηση:

Ο Τάκης μπορεί να σβήσει όλους τους φούρνους χρησιμοποιώντας ~3~ διακόπτες, ως εξής:

1. Χρησιμοποιεί τον ~4~ο διακόπτη, που αντιστρέφει την κατάσταση του ~4~ου και του επόμενου ενός φούρνου. Η κατάσταση των φούρνων γίνεται ~[1,\;0,\;0,\;0,\;0,\;0]~.
2. Χρησιμοποιεί τον ~2~ο διακόπτη, που αντιστρέφει την κατάσταση του ~2~ου και των επόμενων δύο φούρνων. Η κατάσταση των φούρνων γίνεται ~[1,\;1,\;1,\;1,\;0,\;0]~.
3. Χρησιμοποιεί τον ~1~ο διακόπτη, που αντιστρέφει την κατάσταση του ~1~ου και των επόμενων τριών φούρνων. Η κατάσταση των φούρνων γίνεται ~[0,\;0,\;0,\;0,\;0,\;0]~.. Επιπλέον, μπορεί να αποδειχθεί ότι ο Τάκης δεν μπορεί να σβήσει όλους τους φούρνους χρησιμοποιώντας λιγότερους από ~3~ διακόπτες. Επομένως, η απάντηση είναι ~3~.

Περιορισμοί

• ~1 \le N \le 200.000~
• ~0 \le a_i \le 1~
• ~0 \le k_i \le N - i~

Υποπροβλήματα:

1. (11 βαθμοί) ~k_i = 0~ για κάθε ~i~ (όπου ~1 \le i \le N~).
2. (17 βαθμοί) ~a_i = 1~ για κάθε ~i~ (όπου ~1 \le i \le N~).
3. (21 βαθμοί) ~k_i \le 10~ για κάθε ~i~ (όπου ~1 \le i \le N~).
4. (24 βαθμοί) ~k_i = N - 1~ για κάθε ~i~ (όπου ~1 \le i \le N~).
5. (27 βαθμοί) Δεν υπάρχουν περαιτέρω περιορισμοί.

Παρατηρήσεις:

• Μορφοποίηση: Στην είσοδο αλλά και στην έξοδο, κάθε γραμμή τερματίζει με έναν χαρακτήρα newline.
• Μέγιστος χρόνος εκτέλεσης: ~1~ sec.
• Μέγιστη διαθέσιμη μνήμη: ~64~ MB.
• Επικεφαλίδες στον πηγαίο κώδικα: Στην αρχή του πηγαίου κώδικά σας, θα πρέπει να χρησιμοποιήσετε τις παρακάτω επικεφαλίδες.

(* USER: username
LANG: PASCAL
TASK: oven *)

για κώδικα σε PASCAL

/* USER: username
LANG: C
TASK: ovens */

για κώδικα σε C

/* USER: username
LANG: C++
TASK: ovens */

για κώδικα σε C++

/* USER: username
LANG: Java
TASK: ovens */

για κώδικα σε Java

Προσοχή: Η απάντηση μπορεί να υπερβαίνει το ~2^{32}~. Επίσης, φροντίστε να διαβάζετε την είσοδο και να εκτυπώνετε την έξοδο αποδοτικά, ειδικά αν μεταφράζετε σε C++ ή Java.