Tình yêu và những viên đá định mệnh

Ở một vùng đất xa xôi nơi mặt trời mọc, có một chàng trai tên là Haruki. Anh sống bình lặng trong một ngôi làng nhỏ, nơi mà mùa xuân luôn thắm sắc hoa anh đào. Một ngày nọ, Haruki đem lòng yêu một thiếu nữ tên là Aika --- người con gái dịu dàng như làn sương sớm.

Để bày tỏ tình yêu của mình, Haruki quyết định rời làng và bước vào hành trình thu thập các loại đá quý kỳ diệu, rải rác trên con đường dẫn đến Đỉnh Mặt Trăng --- nơi truyền thuyết kể rằng có thể rèn nên món trang sức thiêng liêng chỉ khi hội đủ những viên đá mang tần số hoàn hảo.

Dọc theo hành trình, Haruki thu thập được một chuỗi \(N\) viên đá quý, viên thứ \(i\) thuộc loại \(a_i\). Tuy nhiên, chỉ một số tổ hợp đá nhất định mới có thể hòa hợp để tạo nên món trang sức thần kỳ. Haruki có thể đem cắt bỏ một vài viên đá ở đầu hoặc ở cuối chuỗi. Sau khi cắt, thì chuỗi đá quý của anh phải là một chuỗi đá thiêng.

Một tổ hợp đá là "thiêng" nếu tồn tại:

• Ít nhất một loại đá xuất hiện đúng \(1\) lần,
• Ít nhất một loại xuất hiện đúng \(2\) lần,
• …
• Ít nhất một loại đá xuất hiện đúng \(K\) lần.

Hãy giúp Haruki đếm xem có bao nhiêu cách lựa chọn đoạn liên tiếp trong dãy đá quý sao cho tổ hợp đá còn lại là một tổ hợp thiêng liêng, đủ để rèn món trang sức định mệnh cho Aika.

Input

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên dương \(N\) \((1 \leq N \leq 10^5)\) và \(K\) \((1 \leq K \leq 4)\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) \((1 \leq a_i \leq N)\) --- đại diện cho loại đá quý mà Haruki tìm thấy.

Output

In ra một số nguyên duy nhất --- số cách Haruki có thể chọn đoạn đá thoả điều kiện "thiêng".

Hai lựa chọn khác nhau nếu có ít nhất một vị trí được giữ lại trong một lựa chọn nhưng bị loại bỏ trong lựa chọn kia.

Example

6 2
5 4 5 2 6 5

5

3 1
1 2 1

6

Scoring

• Subtask 1 (14 điểm): \(N \leq 1000\)
• Subtask 2 (16 điểm): \(1 \leq a_i \leq K\) với mọi \(i\)
• Subtask 3 (32 điểm): \(K = 1\)
• Subtask 4 (38 điểm): Không có ràng buộc bổ sung