Migrated from Lutece 1256 昊昊爱运动

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$天内会参加$M$种运动(每种运动用一个$[1,m]$的整数表示)

舍友有$Q$个问题

问昊昊第$l$天到第$r$天参加了多少种不同的运动

Input

输入两个数$N$, $M$ ($1\leq N\leq 2000$, $1\leq M \leq 100$);

输入$N$个数$a_i$表示在第i天昊昊做了第$a_i$类型的运动;

输入一个数$Q$($1\leq Q \leq 10^6$);

输入$Q$行 每行两个数 $l$, $r$($1\leq l \leq r \leq n$);

Output

一共$Q$行

每一行输出一个数 表示昊昊在第$l$天到第$r$天一共做了多少种活动

Samples

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

3
2
3

Resources

第七届ACM趣味程序设计竞赛第二场（正式赛）