Cigle

Σε μια εναλλακτική πραγματικότητα στη Γη 616 ο νεαρός Stjepan ζει μια εντελώς διαφορετική ζωή. Αυτή τη στιγμή είναι εγγεγραμμένος στο ένα μάθημα κατασκευής τούβλων στη Σχολή Τεχνών και Σχεδίου. Όπως κάθε παιδί εκεί, έχει εμμονή με τα μοτίβα. Για παράδειγμα, η εργασία του απαιτεί να χτίσει έναν τοίχο από τούβλα χρησιμοποιώντας ~N~ τούβλα. Δεν θα αρχίσει όμως να χτίζει μέχρι να ικανοποιηθεί με το δισδιάστατο σκίτσο του.
Στο σκίτσο, κάθε τούβλο μπορεί να αναπαρασταθεί ως ορθογώνιο με μοναδίαιο ύψος και πλάτος ~d_i~. Αυτός επιλέγει εκ των προτέρων τη σειρά των τούβλων και αρχίζει να σκιτσάρει από την πιο κάτω σειρά.
Στην πρώτη σειρά θα τοποθετήσει κάποιο αριθμό τούβλων που πηγαίνουν από αριστερά προς τα δεξιά. Στη δεύτερη σειρά θα τοποθετήσει τούβλα από δεξιά προς τα αριστερά και το πρώτο τούβλο στη δεύτερη σειρά θα ευθυγραμμιστεί με το τελευταίο τούβλο στην πρώτη σειρά (οι δεξιές άκρες τους θα ευθυγραμμιστούν). Στη συνέχεια, στην τρίτη σειρά θα τοποθετήσει ξανά τα τούβλα από τα αριστερά στα δεξιά. Το πρώτο τούβλο στην τρίτη σειρά θα ευθυγραμμιστεί με το τελευταίο από τη δεύτερη σειρά αλλά αυτή τη φορά τα αριστερά άκρα. Συνεχίζει αυτή τη διαδικασία μέχρι να μη μείνει κανένα τούβλο. Μπορεί να επιλέξει να χτίσει τοίχο με αυθαίρετο αριθμό σειρών.
O Stjepan χρησιμοποιεί σούπερ τσιμέντο, έτσι ώστε να μπορεί να τοποθετηθεί ένα τούβλο στον τοίχο χωρίς να υπάρχει άλλο τούβλο απευθείας από κάτω. Η ομορφιά του τοίχου είναι ένας αριθμός σημέιων τα οποία αγγίζουν ~4~ τούβλα.
Για μια δεδομένη σειρά τούβλων και τα αντίστοιχα μεγέθη τους βοηθήστε να βρείτε τη μεγαλύτερη δυνατή ομορφιά του τοίχου.

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο ~N~ από την περιγραφή του προβλήματος.
Η δεύτερη γραμμή περιέχει ~N~ ακέραιους αριθμούς ~d_i~ από την περιγραφή του προβλήματος.

Έξοδος

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

Βαθμολογία

Έστω ~M~ το πλάτος του μεγαλύτερου τούβλου. Θα ισχύει ~1 \le M \le 5\,000~ εκτός εάν ορίζεται διαφορετικά.

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	9	~1 \le N \le 20~
2	11	~1 \le N \le 80~
3	13	~ 1 \le N \le 500,\,1 \le M \le 2~
4	15	~ 1 \le N \le 500~
5	52	~1 \le N \le 5\,000~

Παραδείγματα

input

6
2 2 2 1 1 2

output

2

input

13
9 5 2 8 8 2 5 9 9 7 8 5 10

output

5

input

12
5 5 2 3 2 1 1 5 5 2 5 1

output

4

Τοίχος με ομορφιά ~4~ για το τρίτο παράδειγμα