33ος ΠΔΠ Γ' Φάση
Ο πόλεμος των τσιφλικάδων (landfight)

Δύο μεγαλογαιοκτήμονες (τσιφλικάδες) είναι η αιτία μεγάλου πονοκεφάλου για το βασιλιά. Τσακώνονται μεταξύ τους για να αποκτήσουν περισσότερα χωράφια και η ιστορία αυτή δε θα έχει καλή έκβαση. Ο βασιλιάς αναλαμβάνει να βρει λύση στη διαμάχη τους και ζητά τη βοήθεια σας.

Στο δρόμο που ενώνει τα δύο τσιφλίκια υπάρχουν \(N\) χωράφια. Γνωρίζουμε τα οικονομικά στοιχεία κάθε χωραφιού και τα αναπαριστούμε με ακέραιους αριθμούς \(x_1,x_2, \ldots x_N\). Μερικά χωράφια βγάζουν κέρδος, οπότε \(x_i \gt 0\), άλλα έχουν ζημιά, οπότε \(x_i \lt 0\) και κάποια δεν έχουν ούτε κέρδος ούτε ζημιά, οπότε \(x_i = 0\). Οι τσιφλικάδες προφανώς προτιμούν να έχουν στην κατοχή τους χωράφια που βγάζουν κέρδος, παρά χωράφια με ζημιά.

Ο βασιλιάς θέλει να δώσει στον ένα τσιφλικά τα \(L\) χωράφια που είναι κοντινότερα στο τσιφλίκι του, ξεκινώντας δηλαδή από το ένα άκρο του δρόμου και στον άλλο τσιφλικά τα \(R\) χωράφια που είναι κοντινότερα στο δικό του τσιφλίκι, ξεκινώντας δηλαδή από το άλλο άκρο του δρόμου. Φυσικά οι τιμές των \(L\) και \(R\) θα πρέπει να είναι μη αρνητικές και τέτοιες ώστε \(L+R \leq N\). Ο βασιλιάς θέλει να μην αδικήσει κανέναν τσιφλικά, επομένως το άθροισμα των \(x_i\) των \(L\) χωραφιών που δίνει στον έναν θα πρέπει να ισούται με το άθροισμα των \(x_i\) των \(R\) χωραφιών που δίνει στον άλλον. Επίσης θέλει να αφήσει όσο γίνεται λιγότερα χωράφια αδιάθετα.

Ποια είναι η ελάχιστη δυνατή τιμή του \(N-(L+R)\) που μπορεί να επιτευχθεί;

Πρόβλημα:

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του IOI (PASCAL, C, C++, Java) το οποίο θα διαβάζει την τιμή του \(N\) και την ακολουθία των αριθμών \(x_i\) και θα εκτυπώνει την απάντηση στο παρακάτω ερώτημα.

Αρχεία Εισόδου:

Τα αρχείο εισόδου με όνομα landfight.in είναι αρχείο κειμένου με την εξής δομή: Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό \(N\): το πλήθος των χωραφιών. Η επόμενη γραμμή περιέχει \(N\) ακέραιους αριθμούς \(x_i\), χωρισμένους ανά δύο με ένα κενό διάστημα: τα οικονομικά στοιχεία των χωραφιών.

Αρχεία Εξόδου:

Το αρχείο εξόδου με όνομα landfight.out είναι αρχείο κειμένου που περιέχει μία μόνο γραμμή με έναν ακέραιο αριθμό: την απάντηση στο παραπάνω ερώτημα.

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

1^o

landfight.in	landfight.out
7 3 2 5 7 1 6 4	2

Εξήγηση: Μπορούμε να δώσουμε \(L = 3\) χωράφια στον αριστερό τσιφλικά, με άθροισμα \(3+2+5 = 10\) και \(R = 2\) χωράφια στον δεξιό τσιφλικά, πάλι με άθροισμα \(6+4 = 10\). Έτσι μένουν αδιάθετα δύο χωράφια.

2^o

landfight.in	landfight.out
10 5 -2 3 -7 -4 -1 3 -5 6 0	0

Εξήγηση: Μπορούμε να δώσουμε \(L = 4\) χωράφια στον αριστερό τσιφλικά, με άθροισμα \(5-2+3-7=-1\) και \(R = 6\) χωράφια στον δεξιό τσιφλικά, πάλι με άθροισμα \(-4-1+3-5+6+0=-1\). Έτσι δε μένει αδιάθετο κανένα χωράφι.

3^o

landfight.in	landfight.out
5 1 2 3 4 5	5

Εξήγηση: Δεν υπάρχει κανένας τρόπος να δώσουμε \(L\) χωράφια στον έναν και \(R\) χωράφια στον άλλο, έτσι ώστε τα αθροίσματα των \(x_i\) να είναι ίσα. Επομένως και τα \(5\) χωράφια θα μείνουν αδιάθετα.

Περιορισμοί:

• \(1 \leq N \leq 1.000.000\),
• Το άθροισμα των απολύτων τιμών όλων των \(x_i\) δε θα υπερβαίνει το \(10^9\)
• Για περιπτώσεις ελέγχου συνολικής αξίας 20%, θα είναι \(1 \leq N \leq 1.000\)
• Για περιπτώσεις ελέγχου συνολικής αξίας 50%, θα είναι \(1 \leq N \leq 30.000\)
• Για περιπτώσεις ελέγχου συνολικής αξίας 70%, θα είναι \(x_i \gt 0\)

Προσοχή:

Φροντίστε να διαβάζετε την είσοδο και να εκτυπώνετε την έξοδο αποδοτικά, ειδικά αν προγραμματίζετε σε C++ ή Java.

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