Nizin

Do Geese See God? Or, Was It A Rat I Saw? Μη σας νοιάζουν οι χήνες ή οι αρουραίοι, αυτή είναι απλώς μια περιττή εισαγωγή για να επιδείξουμε την αγάπη του Mislav για τα παλίνδρομα. Βοηθήστε τον να λύσει την παρακάτω εργασία!

Έστω ~A~ ένας πίνακας από ~N~ ακεραίους. Λέμε ότι το \(Α\) είναι παλινδρομικό αν για κάθε ~i~ ισχύει ~A[i] = A[N-i+1]~, όπου το ~A[i]~ αντιπροσωπεύει το ~i~-οστό στοιχείο του πίνακα \(Α\) και ο δείκτης του πρώτου στοιχείου στον πίνακα είναι 1.

Ο Mislav μπορεί να τροποποιήσει τον πίνακα με τον ακόλουθο τρόπο: με μία μόνο κίνηση, επιλέγει δύο γειτονικά στοιχεία αυτού του πίνακα και τα αντικαθιστά με το άθροισμά τους. Παρατηρήστε ότι ο αριθμός των στοιχείων στον πίνακα θα μειωθεί κατά 1 μετά από κάθε κίνηση. Ο Mislav θέλει να μάθει ποιος είναι ο ελάχιστος αριθμός κινήσεων που πρέπει να κάνει για να γίνει παλινδρομικός ο αρχικός πίνακας.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο αριθμό ~N~ ~(1 \le N \le 10^6)~ που αντιπροσωπεύει τον αριθμό των στοιχείων στον πίνακα.
Η ακόλουθη γραμμή περιέχει ~N~ θετικούς ακέραιους χωρισμένους σε διάστημα που αντιπροσωπεύουν τα στοιχεία στον πίνακα του Mislav. Οι αριθμοί στην είσοδο θα είναι το πολύ ~10^9~.

Έξοδος

Εξαγάγετε τον ελάχιστο αριθμό κινήσεων που χρειάζεται για να μετατρέψετε τον αρχικό πίνακα σε παλινδρομικό, δεδομένων των κανόνων από την εργασία.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας 30% των συνολικών πόντων, θα ισχύει ~N \le 10~.
Σε περιπτώσεις δοκιμής αξίας 60% των συνολικών πόντων, θα ισχύει ~N \le 1\,000~.

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

input

3
1 2 3

output

1

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

1 2 3 -> 3 3

input

5
1 2 4 6 1

output

1

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

1 2 4 6 1 -> 1 6 6 1

input

4
1 4 3 2

output

2

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

1 4 3 2 -> 5 3 2​ -> 5 5