Chocolate Bar Partition 2

Η Alice και ο Bob παίζουν ένα παιχνίδι με μια σοκολάτα. Αρχικά, η σοκολάτα αποτελείται από ~N~ συνδεδεμένα τετράγωνα κομμάτια σε μία ευθεία γραμμή, όπου το ~A_i~ αντιπροσωπεύει τη γευστικότητα του ~i~-οστού κομματιού. Οι παίκτες παίζουν εναλλάξ, χωρίζοντας τη σοκολάτα, με την Alice να παίζει πρώτη.

Σε μία κίνηση, η Alice μπορεί να επιλέξει οποιοδήποτε συνεχόμενο τμήμα από τετράγωνα κομμάτια σοκολάτας και να το χωρίσει σε δύο ξεχωριστά τμήματα.

Σε μία κίνηση, ο Bob μπορεί να επιλέξει ένα από τα δύο συνεχόμενα τμήματα σοκολάτας που προέκυψαν από τον διαχωρισμό της Alice στην προηγούμενη σειρά του παιχνιδιού και να χωρίσει το επιλεγμένο τμήμα σε δύο ξεχωριστά τμήματα. Αν ο Bob δεν μπορεί να πραγματοποιήσει έναν τέτοιο διαχωρισμό, η σειρά του παραλείπεται.

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

Στόχος της Alice είναι να μεγιστοποιήσει το άθροισμα της γευστικότητας της σοκολάτας που θα πάρει, ενώ στόχος του Bob είναι να ελαχιστοποιήσει το άθροισμα της γευστικότητας που θα πάρει η Alice.

Βρείτε το μέγιστο άθροισμα γευστικότητας που μπορεί να πετύχει η Alice.

Είσοδος

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

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

Ο παρακάτω πίνακας δείχνει πώς κατανέμονται οι ~25~ διαθέσιμοι βαθμοί:

Βαθμοί	Όρια του ~N~
~3~	~1 \le N \le 8~
~7~	~1 \le N \le 200~
~15~	~1 \le N \le 600~

Έξοδος

Εκτυπώστε έναν ακέραιο αριθμό: το μέγιστο άθροισμα γευστικότητας που μπορεί να πετύχει η Alice.

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

input

4
1 2 -4 4

output

4

Επεξήγηση του παραδείγματος:

Η Alice θα χωρίσει τη σοκολάτα σε δύο τμήματα: ~[1,\ 2,\ -4]~ και ~[4]~, και στη συνέχεια θα φάει το τμήμα με γευστικότητα ~4~. Μπορεί να αποδειχθεί ότι η μέγιστη γευστικότητα που μπορεί να πετύχει είναι ~4~.