Cho dãy gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 ≤ a_i ≤ n; i = 1, 2, ..., n~). Một đoạn con tốt gồm 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.

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 ≤ 10^5; k ≤ 4~);

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

Output

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.

Test mẫu

Input

3 1  
1 2 1  

Output

6

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

Input

6 3  
5 6 5 4 5 5  

Output

1  

Giải thích: 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].

Input

6 2  
5 4 5 2 6 5  

Output

5  

Giải thích: 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].

Scoring

Subtask 1 (~30\%~): ~n ≤ 1000~

Subtask 2 (~20\%~): ~1 ≤ a_i ≤ k, ∀i = 1, 2, ..., n~

Subtask 3 (~30\%~): ~k = 1~

Subtask 4 (~20\%~): Không có ràng buộc gì thêm.