吉他与孤独与蓝色星球！

题目描述

长大以后，$\text{Hitori}$ 成为了远近闻名的社交达人！

$\text{Hitori}$ 一共交到了 $m$ 个朋友，每个朋友都有一种独一无二的颜色。为了方便，我们用数字来表示每位朋友的颜色，即：第 $i$ 位朋友的颜色为 $i$ 。

这一天，$\text{Hitori}$ 又在坐地铁。她发现线路图上从左到右一共有 $n$ 个换乘站，第 $i$ 个换乘站对应的线路颜色为 $a_i$ ，并且 $1\leq a_i \leq m$ 。对于这样一个由颜色构成的序列， $\text{Hitori}$ 将其称为整数序列 $a$ 。

$\text{Hitori}$ 想起了她的 $m$ 个朋友，她想知道，在序列 $a$ 中，有多少个长度为 $m$ 的子段，满足在子段中，每位朋友的颜色都恰好只出现了一次。

说明： 一个序列是 $a$ 的子段，当且仅当该序列由若干个 $a$ 中连续的元素按顺序组成。如，$[1, 2, 3]$ 和 $[3, 3, 5]$ 是 $[1, 2, 3, 3, 5]$ 的子段，但 $[1, 3, 5]$ 和 $[1, 3, 2]$ 不是。

输入

输入包含两行。

第一行包含两个整数 $n, m$ ，分别表示序列 $a$ 的长度和 $\text{Hitori}$ 朋友的数量。

第二行包含 $n$ 个整数 $a_1, a_2, a_3, \cdots, a_n\ \ (1\leq a_i \leq m)$，表示颜色序列 $a$ 。

输出

输出一行，包括一个整数，表示满足要求的子段数量。

输入样例 1

5 3
3 2 1 3 1

输出样例 1

2

输入样例 2

5 4
3 2 1 4 3

输出样例 2

2

输入样例 3

2 3
3 1

输出样例 3

0

样例解释

在样例 $1$ 中，长度为 $3$ 的子段有 $3$ 个，分别是 $[3, 2, 1], [2, 1, 3], [1, 3, 1]$ 。

其中 $[3, 2, 1], [2, 1, 3]$ 满足 $3$ 种颜色都恰好出现了一次。

$[1, 3, 1]$ 中，$2$ 没有出现，$1$ 出现了两次，不符合条件。

故答案为 $2$ 。

数据范围

• 对于 $88\%$ 的数据，满足 $1 \leq n, m \leq 5000$
• 对于 $100\%$ 的数据，满足 $1 \leq n, m \leq 10 ^ 6$

题目背景

在北京地铁 $8$ 号线上，$\text{Hitori}$ 发现线路图上 $14$ 号线、$7$ 号线、$2$ 号线和 $1$ 号线的颜色依次是粉色、黄色、蓝色、红色，正好对应了她和她的三个朋友。

只不过为什么粉色要离得比较远呢？

$\text{Hitori}$ 不由得唱起了：

愚昧无知的我唯有放声高歌

倾诉一切吧 对那星辰

——《吉他与孤独与蓝色星球》