Cho mảng gồm 𝑁 N số nguyên dương 𝐴 1 , 𝐴 2 , … , 𝐴 𝑁 A 1 ​

,A 2 ​

,…,A N ​

và một số nguyên 𝐾 K.

Một đoạn con liên tiếp [ 𝐿 , 𝑅 ] [L,R] được gọi là K-dominant nếu tồn tại một giá trị 𝑋 X sao cho:

số lần xuất hiện của 𝑋 X trong đoạn lớn hơn tổng số lần xuất hiện của tất cả các giá trị khác trong đoạn (tức là 𝑓 𝑟 𝑒 𝑞 ( 𝑋 ) > ( 𝑅 − 𝐿 + 1 ) − 𝑓 𝑟 𝑒 𝑞 ( 𝑋 ) freq(X)>(R−L+1)−freq(X))

và đồng thời 𝑓 𝑟 𝑒 𝑞 ( 𝑋 ) ≥ 𝐾 freq(X)≥K.

Hãy đếm số lượng đoạn con K-dominant.

Ràng buộc:

1 ≤ 𝑁 ≤ 2 × 10 5 1≤N≤2×10 5

1 ≤ 𝐴 𝑖 ≤ 10 9 1≤A i ​

≤10 9

1 ≤ 𝐾 ≤ 𝑁 1≤K≤N

Input:

N K A1 A2 ... AN

Output: In ra một số nguyên là số đoạn con K-dominant.

Ví dụ:

Input 6 2 1 2 2 2 3 2

Output 7