CF190D.Non-Secret Cypher

Berland starts to seize the initiative on the war with Flatland. To drive the enemy from their native land, the berlanders need to know exactly how many more flatland soldiers are left in the enemy's reserve. Fortunately, the scouts captured an enemy in the morning, who had a secret encrypted message with the information the berlanders needed so much.

The captured enemy had an array of positive integers. Berland intelligence have long been aware of the flatland code: to convey the message, which contained a number m, the enemies use an array of integers a. The number of its subarrays, in which there are at least k equal numbers, equals m. The number k has long been known in the Berland army so General Touristov has once again asked Corporal Vasya to perform a simple task: to decipher the flatlanders' message.

Help Vasya, given an array of integers a and number k, find the number of subarrays of the array of numbers a, which has at least k equal numbers.

Subarray a[i... j] (1 ≤ i ≤ j ≤ n) of array a = (_a_1, _a_2, ..., a__n) is an array, made from its consecutive elements, starting from the i-th one and ending with the j-th one: a[i... j] = (a__i, a__i + 1, ..., a__j).

伯兰德开始在与弗拉特兰德的战争中掌握主动权。为了将敌人驱逐出其故土，伯兰德人需要准确知道敌方后备部队中还剩下多少弗拉特兰德士兵。幸运的是，清晨侦察兵俘获了一名敌军士兵，他身上携带着一份秘密加密信息——这正是伯兰德人迫切需要的情报。

被俘敌军士兵携带一个正整数数组。伯兰德情报部门早已知晓弗拉特兰德的编码方式：为传递一个包含数字 $m$ 的消息，敌人会使用一个整数数组 $a$，使得该数组中“至少包含 $k$ 个相等数字”的子数组个数恰好等于 $m$。数值 $k$ 早已为伯兰德军队所知，因此图里斯托夫将军再次委派下士瓦夏执行一项简单任务：破译弗拉特兰德人的密信。

请帮助瓦夏：给定一个整数数组 $a$ 和一个数 $k$，求出数组 $a$ 中满足“至少包含 $k$ 个相等数字”的子数组的个数。

数组 $a = (a_1, a_2, \dots, a_n)$ 的子数组 $a[i \dots j]$（其中 $1 \le i \le j \le n$）是由其连续元素构成的数组，起始于第 $i$ 个元素，终止于第 $j$ 个元素：$a[i \dots j] = (a_i, a_{i+1}, \dots, a_j)$。

The first line contains two space-separated integers n, k (1 ≤ k ≤ n ≤ 4·105), showing how many numbers an array has and how many equal numbers the subarrays are required to have, correspondingly.

The second line contains n space-separated integers a__i (1 ≤ a__i ≤ 109) — elements of the array.

第一行包含两个以空格分隔的整数 $n$、$k$（$1 ≤ k ≤ n ≤ 4·10^5$），分别表示数组中元素的个数，以及子数组中要求相等的元素个数。

第二行包含 $n$ 个以空格分隔的整数 $a_i$（$1 ≤ a_i ≤ 10^9$）—— 数组的元素。

Print the single number — the number of such subarrays of array a, that they have at least k equal integers.

Please do not use the %lld specifier to read or write 64-bit integers in С++. In is preferred to use the cin, cout streams or the %I64d specifier.

输出一个整数——即数组 $a$ 中满足“至少包含 $k$ 个相等整数”的子数组的个数。

请注意：在 C++ 中，不要使用 %lld 说明符读取或写入 64 位整数。推荐使用 cin、cout 流，或 %I64d 说明符。

In the first sample are three subarrays, containing at least two equal numbers: (1,2,1), (2,1,2) and (1,2,1,2).

In the second sample are two subarrays, containing three equal numbers: (1,2,1,1,3) and (1,2,1,1).

In the third sample any subarray contains at least one 1 number. Overall they are 6: (1), (1), (1), (1,1), (1,1) and (1,1,1).

第一个样例中有三个子数组，其中至少包含两个相等的数：$(1,2,1)$、$(2,1,2)$ 和 $(1,2,1,2)$。

第二个样例中有两个子数组，其中包含三个相等的数：$(1,2,1,1,3)$ 和 $(1,2,1,1)$。

第三个样例中，任意子数组都至少包含一个数字 $1$。总共共有 6 个：$(1)$、$(1)$、$(1)$、$(1,1)$、$(1,1)$ 和 $(1,1,1)$。