little w and Discretization

题号：NC21758
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小w向大家介绍了离散化处理的具体操作过程。离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。

假设原数组为 $a$ 数组，将其离散化后得到 $b$ 数组，我们要求满足b数组满足以下几点：

离散化数组应保留原数组的大小关系，即当 $a_i>a_j$ 时，必有 $b_i>b_j$ ， $a_i=a_j$ 时，必有 $b_i=b_j$ ， $a_i<a_j$ 时，必有 $b_i<b_j$ 。
$b$ 数组由正整数构成。
在满足以上两点的情况下，b数组的每个元素都要求尽可能的小。

比如说对 $\{100,200,500,200,300\}$ 进行离散化后将会变成 $\{1,2,4,2,3\}$ 。

为了考验大家是不是真的学会了离散处理，小w准备来考考大家。

小w现在有一个长度为 $n$ 的 $a$ 数组，下标从 $1$ 到 $n$ ，并且满足 $a_i\in [1,10^9]$ 。

每次小w会选择一段 $L$ 到 $R$ 的子数组，问，如果把这段子数组进行离散化处理后，将会有多少个元素跟原来不同？

查询彼此独立，不会真的把数值离散化掉。

输入描述:

对于每组案例，首先输入一个正整数

接下来一行个正整数表示a数组每个元素。

接下来一个正整数m，表示小w有个问题

接下来m行，每行两个正整数表示小w选中的子数组由组成，并且问你将其离散化后将会有多少个元素发生改变。

输出描述:

对于每个查询，输出一行一个整数，表示查询的答案。

示例1

输入

复制

9
4 3 1 2 5 3 3 1 4
8
1 3
2 4
2 5
1 5
3 7
4 7
4 8
5 9

输出

复制

说明

第一个查询表示的子数组为{4,3,1}，将其离散化后得到{3,2,1}，有两个元素发生变化。
第二个查询表示的子数组为{3,1,2}，将其离散化后得到{3,1,2}，没有任何元素元素发生变化。
第三个查询表示的子数组为{3,1,2,5}，将其离散化后得到{3,1,2,4}，有一个元素元素发生变化。
第四个查询表示的子数组为{4,3,1,2,5}，将其离散化后得到{4,3,1,2,5}，没有任何元素元素发生变化。
第五个查询表示的子数组为{1,2,5,3,3}，将其离散化后得到{1,2,4,3,3}，有一个元素元素发生变化。
第六个查询表示的子数组为{2,5,3,3}，将其离散化后得到{1,3,2,2}，有四个元素元素发生变化。
第七个查询表示的子数组为{2,5,3,3,1}，将其离散化后得到{2,4,3,3,1}，有一个元素元素发生变化。
第八个查询表示的子数组为{5,3,3,1,4}，将其离散化后得到{4,2,2,1,3}，有四个元素元素发生变化。

备注:

每个查询都是独立的，并不会改变a数组的组成。