题目描述

田所先生非常喜欢shutdown，在shutdown掉同学长达213行的线段树之后。

田所先生突发奇想，决定数一数自己的shutdown程序的一定区间内，有多少种不同shutdown程序。

由于田所先生的shutdown程序很多，所以他想让你帮忙。（由于数据较大，最大点《只有》9.7MB建议使用较快的读入方式和输出方式，亲测scanf比cout快了4倍...）

珍爱生命，远离shutdown

简要题意

给定一串数组 $a$ 和$l,r$，求其中区间$[l,r]$的元素种数。

输入

一行一个正整数 $n$，表示程序个数。 第二行 $n$ 个正整数 $a_i$，表示程序中第 $i$ 种shutdown的种类。

第三行一个整数 $m$，表示田所先生询问的个数。 接下来 $m$ 行，每行两个整数 $l,r$，表示询问的区间。

输出

输出 $m$ 行，每行一个整数，依次表示询问对应的答案。

样例

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

2
2
4

说明

样例1

数据范围