Migrated from Lutece 1342 郭大侠与甲铁城

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

全世界被产业革命的波澜推动，自近世变迁至近代之时，不死的怪物突然出现。被钢铁的皮膜包覆，只要心脏不被破坏就不会消灭，被它啃咬的人似乎也会在死过一次之后复生，并开始袭击人类。之后被称为卡巴内的这些怪物爆发性地增殖，并覆盖了全世界。

远东岛国日本的人们，为了对抗卡巴内的威胁而在各地建造名为“驿”的城寨，并困守在其中，想方设法残存下去。能够在驿之间来往的只有装甲蒸汽机车（通称骏城），驿之间通过各自生产物的融通，总算是保证了生活。

住在以炼铁和蒸汽机的生产为业的显金驿的蒸汽锻冶少年，郭大侠。他为了打倒卡巴内，开发出独自的武器“贯筒”，同时期盼着有朝一日能够发挥出自己的力量。

某天，穿越前线的骏城之一甲铁城来到了显金驿。为了车辆的清扫整备而被召唤的郭大侠，目击到了从义务性的卡巴内检阅中被免除的不可思议少女。

当晚，郭大侠与自称为无名的那位白天的少女再会，此时骏城突然暴走并突入了显金驿。乘务员全灭，而且全部变成了卡巴内！

卡巴内从显金驿中溢出。如同要从被恐慌袭击的人浪中逆行一般，郭大侠奔跑着。这一次不能逃避，我要用贯筒打倒卡巴内！

——于是，为了成为真正能闪耀光辉的男人，郭大侠的战斗开始了。

……

现在在这个城市中有n个卡巴内，每个卡巴内都有他自身的属性a[i]，郭大侠的贯筒能够一次性击穿[L,R]区间中拥有不同属性的怪物！

为了足够强的发挥自己的武器的实力，郭大侠必须提前知道自己的一次性贯筒能够击杀多少只怪物。

现在开始计算吧！

Input

第一行给你n，q，表示有n个卡巴内，q次询问

第二行有n个整数，表示每一个卡巴内的属性a[i]

接下来q行，每行两个整数Li，Ri，表示询问。

$1<=n,q<=100000$

$1<=Li<=Ri<=n$

$1<=a[i]<=10000$

Output

对于每一个询问，输出答案！

Samples

5 3
1 2 3 1 1
1 3
1 4
3 5

3
3
2

Resources

2016 UESTC Training for Data Structures