D. 听音乐

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记错了，没有一个合法的方案）。

第一行两个数n,m。

第二行m个数表示ai。

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

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

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

一个数表示答案。

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

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

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