该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小郡在玩打怪游戏，游戏共有 $n$ 个关卡，每通过一个关卡就会遇到一把武器，它的代号为 $a_i$，表示当你第 $a_i$ 次遇到代号为 $a_i$ 的武器时，才能够获得这把武器（代号相同的武器可以认为是相同的武器）。

现在有 $m$ 次询问，每次指定一个关卡区间 $[L,R]$，在通过这些关卡之后（小郡是一个高手，所以这些关卡都能通过），小郡需要从获得的武器中选出 $k_i$ 个（保证 $k_i ≤ 4$ ）来与怪物对决，你需要输出你有多少种组合方案。

输入格式

第一行输入一个数 $n$ 表示关卡的数量。

第二行输入 $n$ 个整数 $a_i(1 \le a_i \le 10^9)$ 表示第 $i$ 个关卡遇到的武器的代号（保证任意两个武器的代号互不相同）。

第三行输入一个整数 $m$ 表示挑战次数。

接下来的 $m$ 行，每行三个正整数 $L_i, R_i, k_i\;(1 \le L_i \le R_i \le n, 1 \le k_i \le 4)$，表示需要通过的关卡区间。

输出格式

输出 $m$ 行，每行一个整数，表示该次挑战武器组合方案数量。

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

1
0
1
2

说明

【样例解释】

对于第一个询问，获得的武器为 $1$，选出一把武器的方案为 $(1)$；

对于第二个询问，没有获得的武器；

对于第三个询问，获得的武器为 $2$，选出一把武器的方案为 $(2)$；

对于第四个询问，获得的武器为 $1,2$，选出一把武器的方案为 $(1),(2)$ 两种。

【数据范围】

• 测试点 $1-2$，$n \le 50, m \le 50$；
• 测试点 $3-4$，$n \le 1000, m \le 1000$；
• 测试点 $5$，$n \le 10^5, m \le 10^5$，且 $r-l \le 3$；
• 测试点 $6-7$，$n \le 10^5, m \le 10^5$，且 $a_i \le 10$；
• 测试点 $9-10$，$n \le 10^5, m \le 10^5$，无特殊性质。