Scape和Mythological交流了玩几何冲刺的经验之后，Mythological非常高兴，又推荐给Scape一款游戏To the moon。

游戏中一位老人John的记忆被药物尘封，进行了解除尘封的仪式之后，Scape走入了他的记忆。

John的记忆中有一个唤做River女孩的身影，有着数不尽的纸兔子，有一个沙包，一只鸭嘴兽玩偶，一座灯塔。Scape被深深的打动了。

”我的鸭嘴兽和沙包又在哪里呢？” Scape这样想到，不禁幻想出Mythological决定给他送 $n$ 份礼物，其中第 $i$ 份的种类是 $a_i$。这些礼物按顺序排成一行。

她挑选礼物的方式很特别，她每次会选择两份种类相同的礼物，并且这对礼物满足它们之间没有尚未拿走的礼物，并将这对礼物拿走。

现在Scape给出了若干次询问，每次询问如果他送给她的是区间 $[L_i,R_i]$ 之间的礼物，那么她最多能拿走多少份礼物。

任务

你需要编写两个函数/过程，以完成题目的任务：

• init(n, m, a[], t);
  • 在程序最开始运行时会调用一次来完成初始化。
  • $n$ 表示 $a$ 的长度是 $n$，$m$ 表示 $a_i$ 的最大可能值，$a$ 数组的下标从 $1$ 开始，$t$ 表示子任务编号。
• query(l, r);
  • 表示询问区间 $[L,R]$ 的答案 。
  • 保证 $L\le R$。

实现细节

本题只支持 C/C++。

你只能提交一个源文件实现如上所述的 init 和 query 函数/过程，并且遵循下面的命名和接口。你需要包含头文件 mythological.h。

void init(int n, int m, int a[], int t);
int query(int l, int r);

如果有不清楚的地方，见样例及测评库下载，内附了样例程序。

评测库大概需要占用$8\mathtt{\text{MB}}$的内存和$100\mathtt{\text{ms}}$的时间。

因为评测库使用了fread来进行快速读入，所以用命令行输入数据的选手需要在输入数据完毕后用"Ctrl+D"来输入EOF。

评测方式

评测系统将读入如下格式的输入数据：

1. 第 $1$ 行：四个整数 $n,m,q,t$，分别是这组测试数据的大小，$a_i$ 的最大可能值，询问个数和子任务编号。
2. 第 $2$ 行：$n$ 个整数，第 $i$ 个整数表示 $a_i$。
3. 第 $2+i$ 行（$1\le i\le q$）：两个整数 $L_i,R_i$，表示询问的区间。

样例一

input

9 10 3 0
1 1 3 2 1 1 2 3 1
2 9
1 2
2 5

output

8
2
0

样例二

input

10 10 3 0
1 2 3 4 5 6 7 8 9 10
1 9
2 3
4 5

output

0
0
0

样例三

见样例及测评库下载。

限制与约定

对于所有数据，$1\le n\le 1\times {10}^5$，$1\le m\le 1\times {10}^5$，$q\le 2\times {10}^6$，$L_i\le R_i$。

为了拿到每个子任务的分数，你必须通过所有他依赖的子任务。

子任务3生成询问的方式如下：

定义 $$F_i=(2000i^2+629i+2333)modn+1$$

则对所有的 $1\le i\le q$，有 $$L_i=min\{F_{2i-1},F_{2i}\}$$ $$R_i=max\{F_{2i-1},F_{2i}\}$$

交互式类型的题目怎么本地测试

时间限制：$2\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载