Učiteljica

Στο καλύτερο σχολείο σε όλο το Βαραζντίν, υπήρχε μια εξαιρετική καθηγήτρια πληροφορικής γνωστή για τις ενδιαφέρουσες και ασυνήθιστες ιδέες της. Το όνομά της ήταν Λάνα, και συχνά έδινε στους μαθητές της αδύνατα ή άλυτα προβλήματα. Κάθε μαθητής έπρεπε να λύσει μόνο ένα πρόβλημα κατά τη διάρκεια της σχολικής χρονιάς για να περάσει το μάθημα με άριστο βαθμό. Οι μαθητές που δεν έλυναν κανένα πρόβλημα μέχρι το τέλος της χρονιάς θα έπρεπε να επαναλάβουν την τάξη. Την τελευταία μέρα του σχολείου, έγραψε ένα εξαιρετικά δύσκολο πρόβλημα στον πίνακα, το οποίο είχε ως εξής:

Φανταστείτε ότι έχετε μια ακολουθία αριθμών μήκους ~N~, και μπορείτε να αφαιρέσετε κάποια στοιχεία από την αρχή ή το τέλος (ή και τα δύο). Με πόσους τρόπους μπορείτε να πραγματοποιήσετε τέτοιες διαγραφές, έτσι ώστε μετά τη διαγραφή να υπάρχει τουλάχιστον ~1~ αριθμός που να εμφανίζεται ακριβώς μία φορά, τουλάχιστον ~1~ αριθμός που να εμφανίζεται ακριβώς δύο φορές, ..., και τουλάχιστον ~1~ αριθμός που να εμφανίζεται ακριβώς ~K~ φορές.

Ένας μαθητής ονόματι Φραν, που δεν είχε λύσει κανένα πρόβλημα μέχρι τότε, είπε πολύ γρήγορα, "Ξέρω πώς να λύσω αυτό το πρόβλημα!" Η δασκάλα, η κυρία Λάνα, δεν τον πίστεψε και του είπε, "Γράψε τον κώδικα στα επόμενα ~30~ λεπτά, και τότε θα σε πιστέψω. Αν δεν το κάνεις, θα πρέπει να επαναλάβεις την τάξη." Ο Φραν δεν ξέρει πώς να προγραμματίζει, γι' αυτό ζήτησε επειγόντως τη βοήθειά σου για να γράψεις τον κώδικα και να λύσεις αυτό το πρόβλημα. Στη βιασύνη του, ξέχασε να εξηγήσει την ιδέα του για την επίλυση του προβλήματος. Γράψε έναν κώδικα που θα παίρνει ως είσοδο τους αριθμούς ~N~ και ~K~, την ακολουθία των ~N~ στοιχείων, και θα λύνει το ερώτημα της Λάνα, ώστε να βοηθήσεις τον Φραν.

Είσοδος

Στην πρώτη γραμμή, θα υπάρχουν ~2~ θετικοί ακέραιοι ~N\;(1\le N \le 10^5)~ και ~K\;(1\le K \le 4)~ από την περιγραφή της άσκησης.

Στη δεύτερη γραμμή, θα υπάρχουν ~N~ θετικοί ακέραιοι ~a_i\;(1 \le a_i \le N)~, οι αριθμοί από την περιγραφή της άσκησης.

Έξοδος

Στην πρώτη γραμμή, εκτυπώστε έναν ακέραιο αριθμό, τον αριθμό των διακριτών διαγραφών έτσι ώστε να πληρούνται οι συνθήκες της άσκησης. Δύο διαγραφές είναι διαφορετικές αν υπάρχει ένας δείκτης που δεν έχει διαγραφεί στη μία, αλλά έχει διαγραφεί στην άλλη.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~20~	~N \le 1000~
~2~	~15~	~1 \le a_i \le k~ για όλα τα ~i = 1, 2, ... , N~
~3~	~35~	~K = 1~
~4~	~50~	Κανένας επιπλέον περιορισμός.

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

1ο

input

3 1
1 2 1

output

6

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

Οι δυνατές ακολουθίες μετά τη διαγραφή είναι: ~[1]~, ~[2]~, ~[1]~, ~[1, 2]~, ~[2, 1]~, ~[1, 2, 1]~, και σε κάθε μία από τις ~6~ ακολουθίες, υπάρχει ένας αριθμός που εμφανίζεται ακριβώς μία φορά.

2ο

input

6 3
6 5 6 4 5 5

output

1

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

Η μόνη ακολουθία μετά τη διαγραφή στην οποία υπάρχει τουλάχιστον ~1~ αριθμός που εμφανίζεται ακριβώς μία φορά, τουλάχιστον ~1~ αριθμός που εμφανίζεται ακριβώς δύο φορές και τουλάχιστον ~1~ αριθμός που εμφανίζεται ακριβώς τρεις φορές είναι η δοσμένη ακολουθία των ~N~ αριθμών.

3ο

input

6 2
5 4 5 2 6 5

output

5