题目描述

某知名连锁超市在城市中开设了两家位置相邻的分店。在过去的一段时间内，两家分店各自记录了连续 $N$ 个小时的顾客购物数据，第 $i$ 个小时内购买的核心商品编号为 $a_i$。

为了分析两家分店在不同时间段内的商品热度重合度，数据分析师提出了 $Q$ 组商业询问。每组询问会读入四个整数 $l_1,r_1,l_2,r_2$，分别代表第一家分店的观察时间段 $[l_1,r_1]$ 以及第二家分店的观察时间段 $[l_2,r_2]$。

两家分店在各自指定时间段内的商品契合指数定义为：对于所有可能出现的商品编号 $x$，第一家分店在 $[l_1,r_1]$ 期间购买商品 $x$ 的小时数，与第二家分店在 $[l_2,r_2]$ 期间购买商品 $x$ 的小时数的乘积之和。

如果用 $\text{get}(l,r,x)$ 表示在时间区间 $[l,r]$ 内商品编号 $x$ 出现的次数，则商品契合指数的计算公式为：

$$\sum\limits_{x=0}^\infty \text{get}(l_1,r_1,x)\times \text{get}(l_2,r_2,x)$$

现在请你编写程序，帮分析师计算出每组询问下的商品契合指数。

输入格式

第一行，一个数字 $N$，表示序列长度。
第二行，$N$ 个数字，表示 $a_1\sim a_N$。
第三行，一个数字 $Q$，表示询问个数。
第 $4\sim Q+3$ 行，每行四个数字 $l_1,r_1,l_2,r_2$，表示询问。

输出格式

对于每组询问，输出一行一个数字，表示商品契合指数。

样例

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

4
1

说明/提示

对于 $20\%$ 的数据，$1\leq N,Q\leq 1000$；
对于另外 $30\%$ 的数据，$1\leq a_i\leq 50$；
对于 $100\%$ 的数据，$N,Q\leq 50000$，$1\leq a_i\leq N$，$1\leq l_1\leq r_1\leq N$，$1\leq l_2\leq r_2\leq N$。

注意： 答案有可能超过 int 的最大值。