← 返回题目列表

Codeforces · 190/D

D. 非秘密密码

中文机器翻译题面 查看原题

Berland开始在与Flatland的战争中掌握主动权。为了将敌人赶出自己的祖国,伯兰德人需要确切地知道敌人的预备队中还剩下多少平地士兵。幸运的是,侦察兵在早上捕获了一名敌人,他有一条秘密的加密信息,其中包含伯兰德人急需的信息。

被捕获的敌人有一个正整数数组。 Berland情报部门很早就知道平地密码:为了传达消息,其中包含数字m,敌人使用整数数组a。它的子数组(其中至少有 k 个相等的数字)的数量等于 m。数字k在贝尔兰军队中早已广为人知,因此图什托夫将军再次要求瓦夏下士执行一项简单的任务:破译平地人的信息。

帮助 Vasya,给定一个整数数组 a 和数字 k,找到数字数组 a 的子数组的数量,其中至少有 k 个相等的数字。

数组 a = (a1, a2, ..., an) 的子数组 a[i... j] (1 ≤ i ≤ j ≤ n) 是一个由连续元素组成的数组,从第 i 个元素开始到第 j 个元素结束:a[i... j] = (ai, ai + 1, ..., aj)。

输入

第一行包含两个空格分隔的整数n, k (1 ≤ k ≤ n ≤ 4·105),分别表示一个数组有多少个数字以及子数组需要有多少个相等的数字。

第二行包含 n 个空格分隔的整数 ai (1 ≤ ai ≤ 109) — 数组的元素。

输出

打印单个数字 — 数组 a 的此类子数组的数量,它们至少具有 k 个相等的整数。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

4 2
1 2 1 2

输出 #1

3

输入 #2

5 3
1 2 1 1 3

输出 #2

2

输入 #3

3 1
1 1 1

输出 #3

6

注意

第一个样本中有三个子数组,至少包含两个相等的数字:(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)。