给定一个长度 $n$ 的序列 $a_1,\dots,a_n$。
共有 $m$ 次询问，每次询问给定 $l,r$，求区间 $[l,r]$ 中有多少 子区间 $[i,j]$ 满足 $l\le i\le j\le r$，且在区间 $[i,j]$ 内出现过的数的个数为奇数。
输入格式
第一行一个整数 $n$。
接下来一行 $n$ 个整数表示序列 $a_1,\dots,a_n$
接下来一行一个整数 $m$。
接下来 $m$ 行，每行两个整数 $l\;r$ 表示一个询问。
输出格式
对每个询问，输出一行，包含一个整数，表示答案。
样例数据
样例 1 输入
5 2 3 5 1 5 5 2 3 1 1 1 3 2 5 2 4
样例 1 输出
2 1 4 6 4
样例 2 输入
10 2 8 5 1 10 5 9 9 3 5 10 6 8 1 2 3 5 5 7 1 7 3 9 4 9 1 4 3 7 2 5
样例 2 输出
4 2 4 4 16 16 12 6 9 6
子任务
Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078
对于 $25\%$ 的数据，满足 $1\le n,m\le 10^2$。
对于 $50\%$ 的数据，满足 $1\le n,m\le 10^4$。
对于另外 $25\%$ 的数据，满足序列中出现过的数个数不超过 $100$。
对于 $100\%$ 的数据，满足 $1\le n\le 10^6$，$1\le m\le 10^6$，$1\le a_i\le n。$
对每个询问满足 $1\le l\le r\le n$。
以上所有数值为整数。