Description

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

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

Input Format

第一行输入一个整数 n 表示关卡的数量。 第二行输入 n 个整数 ai $( 1 ≤ ai ≤ 10^9 )$ 表示第 i 个关卡遇到的武器的代号(保证任意两 个武器的代号互不相同)。 第三行输入一个整数 m 表示挑战次数。 接下来的 m 行， 每行三个正整数 Li , Ri , ki (1 ≤ Li ≤ Ri ≤ n, 1 ≤ ki ≤ 4) ，表示需要通 过的关卡区间。

Output Format

输出 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

Hint

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