题目描述

定义一个长度为 $k$ 值域为 $[1,m]\cap \mathbb Z_+$ 的字符串 $s$ 的生成字符串为，枚举所有大小为 $m$ 的排列 $p$，字典序最小的 $p_{s_1}p_{s_2}\dots p_{s_k}$。

有一个长度为 $n$ 值域为 $[1,m]\cap \mathbb Z_+$ 的字符串 $S$，你需要求出其所有子串的生成字符串的种类数。

输入格式

第一行两个正整数 $n,m$，表示字符串长度与值域大小，接下来一行 $n$ 个正整数表示字符串 $S$。

输出格式

输出一行一个正整数表示答案。

样例输入 1

5 3
1 2 3 2 1

样例输出 1

7

样例输入 2

6 3
1 2 3 1 3 2

样例输出 2

10

样例输入 3

10 10
1 2 3 4 5 6 7 8 9 10

样例输出 3

10

样例解释

对于第一组样例，总共有如下本质不同的生成字符串：

• $[1]$：$[1],[2],[3],[2],[1]$；
• $[1,2]$：$[1,2],[2,3],[3,2],[2,1]$；
• $[1,2,3]$：$[1,2,3],[3,2,1]$；
• $[1,2,1]$：$[2,3,2]$；
• $[1,2,3,2]$：$[1,2,3,2]$；
• $[1,2,1,3]$：$[2,3,2,1]$；
• $[1,2,3,2,1]$：$[1,2,3,2,1]$。

数据范围

本题采用捆绑测试。

对于所有测试点：

• $1\leq m\leq n$；
• $1\leq n \leq 2\times10^5$。

8s / 2048MB