异度之刃
时间限制:C/C++/Rust/Pascal 5秒,其他语言10秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
64bit IO Format: %lld

题目描述

在被云海覆盖,城市建立在巨神兽上的世界------Alrest,人类的生存空间极为有限。可巨神兽寿命也在不断的减少,它们接连迎来生命的终结,沉下云海,不少人类为了生存开始征服其他的巨神兽。故事的开始,莱克斯被邀请参与天之圣杯打捞行动,在遇见封印的天之圣杯------焰。莱克斯被充满忧郁悲伤气质的美丽少女吸引,出于感恩及倾慕,还有内心对于乐园的向往,决定协助她"回家"。

莱克斯从此成为了一名御刃者,踏上了通往乐园的征程,身为一名合格的御刃者,熟练的使用不同的武技打出御刃者连击是必要的。假设可以用不同的数字表示不同的武技,那么一种御刃者连击就可以表示为一段连续上升的数字串,例如 等。不同的连续上升数字串所表示的御刃者连击是不一样,当两个数字串的长度不同,或者所包含的数字集合不完全一致时,被定义为不一样。为了更好的应对战斗中的各种情况,莱克斯预设了一整套的武技出招表,用序列a_i表示。当然,这里面也包含了各种的御刃者连击。

例如,当

本质不同的连续上升子串有 ,对应了十一种不同的御刃者连击。

现在他想知道,如果截取 a_i 的区间 ,这里面多少种不一样的御刃者连击。

输入描述:

第一行为两个数  ,分别表示数组长度及询问次数

第二行共 n 个数,表示数组 

接下来 q 行,每行两个数 

输出描述:

q 行,每行一个数,表示对应询问的答案
示例1

输入

复制
7 6
1 2 4 5 1 2 3
1 2
1 3
2 4
1 5
4 7
1 7

输出

复制
3
4
4
6
7
9
示例2

输入

复制
3 4
1 2 1
1 1
1 3
1 2
2 3

输出

复制
1
3
3
2

备注:

本题读入量较大,推荐加上读入优化