An là một cậu bé thông minh và rất yêu thích Toán học. Một buổi sáng cậu đang chơi với một dãy số nguyên thì cậu chợt nảy ra một ý tưởng. Cho dãy gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le n; i = 1, 2, \dots, n)~. Ta có thể xóa đi một số phần tử ở đầu hoặc ở cuối hoặc ở cả hai đầu của dãy số. Cho biết có bao nhiêu cách thực hiện xóa sao cho sau khi xóa, dãy thu được có ít nhất ~1~ số xuất hiện đúng một lần, ít nhất ~1~ số xuất hiện đúng hai lần, ~\dots~, và có ít nhất ~1~ số xuất hiện đúng ~k~ lần.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n, k~ ~(n \le 10^5; k \le 4)~;

• Dòng thứ hai gồm ~n~ số nguyên dương ~a_i~ ~(1 \le a_i \le n)~ là giá trị của các phần tử của dãy số ban đầu.

Hai số ghi trên cùng một dòng được phân cách nhau bởi một dấu cách.

Output

Ghi ra một số nguyên là số lượng dãy số sau khi thực hiện xóa thỏa mãn yêu cầu của đầu bài. Hai cách xóa gọi là khác nhau nếu tồn tại một vị trí mà không được xóa ở lần này, nhưng được xóa ở lần khác.

Scoring

Sample Input 1

3 1
1 2 1

Sample Output 1

6

Sample Input 2

6 3
6 5 6 4 5 5

Sample Output 2

1

Sample Input 3

6 2
5 4 5 2 6 5

Sample Output 3

5

Notes

~6~ dãy số thỏa mãn là: ~[1]~; ~[2]~; ~[1]~; ~[1,2]~; ~[2,1]~; ~[1,2,1]~.