You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

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

Format

Input

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

第二行输入 $n$ 个整数 $a_i$ （1 ≤ $a_i$ ≤ $10^9$）表示第 $i$ 个关卡遇到的草莓刀的代号（保证任意两个草莓刀的代号互不相同）。

第三行输入一个整数 $m$ 表示挑战次数。 接下来的 $m$ 行，每行三个正整数 $L_i$, $R_i$, $K_i$ (1 ≤ $L_i$ ≤ $R_i$ ≤$n$,1 ≤ $k_i$ ≤ $4$),表示需要通过的关卡区间。

Output

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

Samples

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

1
0
1
2

备注

对于第一个询问，获得的草莓刀为 1 ，选出一把草莓刀的方案为 (1)

对于第二个询问，没有获得的草莓刀。

对于第三个询问，获得的草莓刀为 2，选出一把草莓刀的方案为 (2)

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

备注：