99991301 - 听音乐

通过次数

9

提交次数

28

Time Limit : 1 秒
Memory Limit : 128 MB

LYK喜欢听音乐,总共有n首音乐,有m个时刻,每个时刻LYK会听其中一首音乐,第i个时刻会听第ai首音乐。它给自己定了一个规定,就是从听音乐开始,听的每连续n首音乐都是互不相同的。例如当n=3时,从听歌开始,123321就是一个合法的顺序(此时LYK听了两轮歌,分别是123和321,每一轮的歌都是互不相同的),而121323就是一个不合法的顺序(LYK也听了两轮歌,第一轮中121存在听了两次相同的歌)。我们现在只截取其中一个片段,也就是说并不知道LYK之前已经听了什么歌。因此121323也仍然可以是一个合法的顺序,因为LYK之前可能听过3,然后再听121323,此时LYK听了三轮歌,分别是312,132和3。

现在LYK将告诉你这m个时刻它听的是哪首歌。你需要求出LYK在听这m首歌之前可能听过的歌的不同方案总数(我们认为方案不同当且仅当之前听过的歌的数量不同)。LYK向你保证它之前听过的歌的数量是在0~n-1之间的。因此你输出的答案也应当是0~n中的某个整数(答案是0表示LYK记错了,没有一个合法的方案)。

Input

第一行两个数n,m。

第二行m个数表示ai。

对于50%的数据n,m<=1000。

对于100%的数据1<=n,m<=100000,1<=ai<=n。

其中均匀分布着n<m以及n>=m的情况。

Output

一个数表示答案。

Examples

Input

4 10
3 4 4 1 3 2 1 2 3 4

Output

1

Input

6 6
6 5 4 3 2 1

Output

6

Hint

样例解释1:LYK之前一定只听过2首歌(12或者21),这样可以分成3部分分别是34,4132,1234,每一部分都没有出现相同的歌。对于其它情况均不满足条件。

样例解释2:LYK之前听过0~5首歌的任意几首都是有可能满足条件的。

提示: LYK知道这个题目很长,但为了便于理解已经加了很多注释了……建议没看懂的同学们再重新看一遍……