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

题目描述

强哥在玩打怪游戏，游戏共有 $𝑛$ 个关卡，每通过一个关卡就会遇到一把武器，它的代 号为 $𝑎_𝑖$ 。

表示当你第 $𝑎_𝑖$ 次遇到代号为 $𝑎_𝑖$ 的武器时，才能够获得这把武器(代号相同的武 器可以认为是相同的武器)。 举个例子，这个区间有6个数:1,2,5,5,5,5 你只能 获得 武器 1 ，你会碰到武器1一次可以获得 武器2碰到一次无法获得，武器5碰到4次无法获得

现在有 $𝑚$ 次询问，每次指定一个关卡区间 $[𝐿,𝑅]$，在通过这些关卡之后(假设强哥是一个 高手，所以这些关卡都能通过)，强哥需要从获得的武器中选出 $𝑘_𝑖$ 个(保证$𝑘_𝑖$ ≤ 4 ) 来与怪物对决，你需要输出你有多少种组合方案。

输入格式(e.in)

第一行输入一个整数 𝑛表示关卡的数量

第二行输入 𝑛 个整数 $𝑎_𝑖$(1 ≤ $𝑎_𝑖$ ≤ $10^9$)表示第 𝑖 个关卡遇到的武器的代号(保证任意两 个武器的代号互不相同)。

第三行输入一个整数 𝑚表示挑战次数。 接下来的 𝑚 行，每行三个正整数 $𝐿_𝑖,𝑅_𝑖,𝑘_𝑖$ ($1 ≤ 𝑘_𝑖$ ≤ 4,$1 \le 𝐿_𝑖,𝑅_𝑖 \le n$) ，表示需要通 过的关卡区间。

输出格式(e.out)

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

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)

对于第二个询问，没有获得的武器,第二个询问会碰到武器3，7，2，3 对于武器3你碰到的次数为2次所以不会获得，对于其他2个武器同理

对于第三个询问，获得的武器为2，选出一把武器的方案为（2）

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

以下为10个测试点的信息