23ος ΠΔΠ Καμπ (juniors)
Άθροισμα παρεμβαλλομένων (intvsum)

Δίνεται μία ακολουθία \(a_1, \ldots , a_N\) αποτελούμενη από \(N\) θετικούς ακέραιους αριθμούς. Ζητείται να διαπιστωθεί αν υπάρχουν θέσεις \(i\) και \(j\), με \(i < j\), τέτοιες ώστε \(a_i + a_j = a_{i+1} + ... + a_{j-1}\), δηλαδή το άθροισμα των αριθμών στις θέσεις \(i\) και \(j\) της ακολουθίας να ισούται με το άθροισμα των αριθμών στις θέσεις που παρεμβάλλονται μεταξύ των \(i\) και \(j\). Αν υπάρχουν πολλά τέτοια ζεύγη θέσεων \((i, j)\) στην ακολουθία, ζητείται να υπολογισθεί η μέγιστη θέση j για την οποία ισχύει η παραπάνω σχέση.

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

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

Αρχεία Εξόδου (intvsum.out):

Η έξοδος πρέπει να αποτελείται από μία γραμμή που να περιέχει ακριβώς έναν ακέραιο αριθμό \(j\), που να αντιστοιχεί στη μέγιστη θέση της ακολουθίας για την οποία υπάρχει θέση \(i\) (με \(i < j\)), έτσι ώστε \(a_i + a_j = a_{i+1} + ... + a_{j-1}\). Αν δεν υπάρχει τέτοια θέση, η έξοδος πρέπει να είναι \(0\).

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

1^o

intvsum.in	intvsum.out
10 78 14 8 1 2 32 16 45 47 64	8

2^o

intvsum.in	intvsum.out
10 3 6 1 2 5 1 4 7 14 8	9

3^o

intvsum.in	intvsum.out
10 256 128 64 32 16 32 64 128 256 512	0

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

• \(3 \leq N \leq 100.000\).
• Όριο χρόνου εκτέλεσης: \(1\) sec.
• Όριο μνήμης: \(16\) MB.