Heavy Light Decomposition

Σε έναν πίνακα που περιέχει μόνο θετικούς ακέραιους, λέμε ότι ένας ακέραιος είναι βαρύς αν εμφανίζεται περισσότερες από μία φορές στον πίνακα και ελαφρύς διαφορετικά.

Ένας πίνακας είναι καλός αν οι ακέραιοι που περιέχει εναλλάσσονται μεταξύ ελαφριών και βαριών.

Δίνεται ένας πίνακας ~a_1, \ldots, a_N~. Να υπολογίσετε τον αριθμό των τρόπων με τους οποίους μπορούμε να τον χωρίσουμε σε έναν αριθμό από συνεχόμενα υποδιαστήματα, έτσι ώστε κάθε υποδιάστημα, όταν θεωρείται ως ανεξάρτητος πίνακας, να είναι καλό.

Επειδή η απάντηση μπορεί να είναι μεγάλη, να την εμφανίσετε modulo ~1.000.003~.

Είσοδος

Η πρώτη γραμμή της εισόδου περιέχει έναν ακέραιο ~N~.

Η επόμενη γραμμή περιέχει ~N~ ακέραιους αριθμούς ~a_1, \ldots, a_N~ (~1 \le a_i \le N~).

Έξοδος

Να εμφανίσετε τον αριθμό των τρόπων με τους οποίους μπορεί να χωριστεί ο πίνακας σε καλά συνεχόμενα υποδιαστήματα, modulo ~1.000.003~.

Βαθμολογία

Βαθμοί	Περιορισμοί	Επιπλέον περιορισμοί
~3~	~2 \le N \le 50.000~	Για κάθε ~i~, ισχύει ~a_i \le 26~.
~4~	~2 \le N \le 5000~	Δεν υπάρχουν επιπλέον περιορισμοί.
~5~	~2 \le N \le 500.000~	Αν το ~i~ είναι περιττό, τότε ~a_i = 1~.
~6~	~2 \le N \le 500.000~	Κάθε αριθμός εμφανίζεται το πολύ δύο φορές στον πίνακα.
~7~	~2 \le N \le 500.000~	Δεν υπάρχουν επιπλέον περιορισμοί.

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

input

5
1 2 3 2 3

output

4

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

Υπάρχουν τέσσερις έγκυροι τρόποι να χωριστεί ο πίνακας ~[1, 2, 3, 2, 3]~:

• ~[1], [2], [3], [2], [3]~
• ~[1], [2,\ 3,\ 2], [3]~
• ~[1], [2], [3,\ 2,\ 3]~
• ~[1,\ 2,\ 3,\ 2], [3]~

input

5
1 2 1 3 1

output

6