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~). Một đoạn con tốt là các phần tử liên tiếp của dãy sao cho:

• Í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;
• ...
• Ít nhất ~1~ số xuất hiện đúng ~k~ lần.

Hai đoạn con được gọi là khác nhau nếu tồn tại chỉ số đầu hoặc cuối của đoạn khác nhau.

Yêu cầu: Hãy đếm số đoạn con tốt của dãy đã cho.

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~).

Output

Ghi ra một số nguyên là số lượng đoạn con tốt thỏa mãn yêu cầu của đề bài.

Sample Input 1

3 1
1 2 1

Sample Output 1

6

Có 6 đoạn con tốt thỏa mãn là: ~[1]; [2]; [1]; [1, 2]; [2, 1]; [1, 2, 1]~.

Sample Input 2

6 3
6 5 6 4 5 5

Sample Output 2

1

Chỉ có 1 đoạn con tốt duy nhất gồm toàn bộ các số là: ~[6, 5, 6, 4, 5, 5]~.

Sample Input 3

6 2
5 4 5 2 6 5

Sample Output 3

5

Có 5 đoạn con tốt là: ~[5, 4, 5]; [5, 4, 5, 2]; [5, 4, 5, 2, 6]; [4, 5, 2, 6, 5]; [5, 2, 6, 5]~.

Ràng buộc

• Subtask 1 (30% số điểm): ~n \le 1000~;
• Subtask 2 (20% số điểm): ~1 \le a_i \le k, \forall i = 1, 2, \dots, n~;
• Subtask 3 (30% số điểm): ~k = 1~;
• Subtask 4 (20% số điểm): Không có ràng buộc gì thêm.