Izbori

Ο κύριος Malnar είναι υποψήφιος δήμαρχος της κομητείας Τομπογέφτσι. H κομητεία Τομπογέφτσι αποτελείται από ένα χωριό (που ονομάζεται Tompojevci), το οποίο αποτελείται από μια σειρά από ~n~ σπίτια με ακέραιους αριθμούς από το 1 έως το ~n~. Σε κάθε σπίτι υπάρχει ένας κάτοικος, αλλά το πιο σημαντικό για τον κ. Malnar, ένας ψηφοφόρος. Ο κύριος Malnar γνωρίζει ότι οι εκλογές δεν κερδίζονται από τον καλύτερο υποψήφιο, αλλά από τον υποψήφιο που διοργανώνει το καλύτερο συμπόσιο πριν τις εκλογές. Ως εκ τούτου, λίγες μέρες πριν τις εκλογές θα διοργανώσει ένα συμπόσιο. Θα καλέσει όλους τους κατοίκους του χωριού που μένουν σε σπίτια των οποίων ο αριθμός είναι μεταξύ ~l~ και ~r\;(l \le r)~ και θα ετοιμάσει ένα νόστιμο γεύμα για αυτούς.

Ο κύριος Malnar γνωρίζει πολύ καλά όλους τους κατοίκους του Τομπογέφτσι, επομένως ξέρει ποιο είναι το αγαπημένο πιάτο του καθενός. Γι' αυτό για το συμπόσιο θα ετοιμάσει το γεύμα που είναι το αγαπημένο της πλειοψηφίας των προσκεκλημένων. Ωστόσο, μόνο όσοι έχουν το αγαπημένο τους γεύμα θα ψηφίσουν τον κύριο Malnar, ενώ οι υπόλοιποι θα ψηφίσουν τον μοναδικό άλλο υποψήφιο, τον κ. Vlado. Για να κερδίσει τις εκλογές, ο κ. Ο Malnar πρέπει να πάρει αυστηρά περισσότερες από τις μισές ψήφους από τους ανθρώπους που ψήφισαν. Οι κάτοικοι που δεν προσκλήθηκαν στο συμπόσιο θα ξεχάσουν τις εκλογές και δεν πρόκειται να ψηφίσουν.

Ο κύριος Malnar θέλει τώρα να μάθει πόσοι διαφορετικοί τρόποι υπάρχουν για να επιλέξει τους αριθμούς ~l~ και ~r~ ώστε να κερδίσει τις εκλογές.

Είσοδος

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

Η δεύτερη γραμμή περιέχει ~n~ θετικούς ακέραιους ~a_i\;(1 \le a_i \le 10^9)~ που ο καθένας αντιπροσωπεύει το αγαπημένο πιάτο του κάτοικου στο σπίτι ~i~.

Έξοδος

Στη μοναδική γραμμή εκτυπώστε τον αριθμό των διαφορετικών τρόπων που μπορεί ο κ. Malnar να επιλέξει τους αριθμούς ~l~ και ~r~ έτσι ώστε να κερδίσει τις εκλογές.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	10	~1 \le n \le 300~
2	15	~1 \le n \le 2000~
3	15	~1 \le a_i \le 2~ για κάθε ~1 \le i \le n~
4	70	Κανένας επιπλέον περιορισμός.

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

input

2
1 1

output

3

input

3
2 1 2

output

4

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

Οι πιθανές επιλογές για ~(l,\;r)~ είναι: ~(1,\;1),\;(2,\;2),\;(3,\;3),\;(1,\;3)~.

input

5
2 2 1 2 3

output

10