선천적 얼간이들

시간 제한 3초

호주까지가서 돈을 벌려던 카츠파트는 치즈공장에 취직했다가 과로사 직전에 그만두었다.

악덕사장 admin에 속아 koistudy에 입사(사실 노예 계약)한 카츠파트는, 수열에 쿼리를 처리하는 일을 하고있다.

하지만 오늘은 비가와서 카츠파트는 심신이 붕괴되어 사경을 헤매게 되었다!

불쌍한 카츠파트를 위해 쿼리를 대신 처리해 주자.

input

첫째줄에 수열의 길이 a와 쿼리의 개수b가 주어진다.(1<=a,b<=100000)

다음줄에 길이a의 수열 X가 주어진다.(1<=Xi<=1000000)

이후 b줄에 걸쳐 정수 2개로 이루어진 쿼리Ci Di가 출력된다.(1<=Ci<=Di<=a)

output

b줄에 걸쳐서 XCi~XBi 사이의 서로다른 정수가 몇 종류 있는지 출력하시오


example

10 5

2 2 4 3 6 7 8 1 1 1
1 2
1 10
2 9
3 5
1 5

답
2 2//1~2번에서 가장 큰 수는 2이고, 2번 나온다
8 1//1~10번에서 가장 큰 수는 8이고 1번 나온다
8 1
6 1
6 1