题目描述

白浅妹妹在玩打怪游戏，游戏共有n个关卡，每通过一个关卡就会遇到一把武器，它的代
号为ai，表示当你第ai次遇到代号为ai的武器时，才能够获得这把武器（代号相同的武器可以认为是相同的武器）。
现在有m次询问，每次指定一个关卡区间 [L, R]，在通过这些关卡之后（白浅妹妹是一个
高手，所以这些关卡都能通过），白浅妹妹需要从获得的武器中选出ki个（保证ki≤ 4 ）
来与怪物对决，你需要输出你有多少种组合方案。
注：同类武器只能同时拥有一把。

输入格式

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

输出格式

【输出格式】
输出 m 行，每行一个整数，表示该次挑战武器组合方案数量。
【样例说明】
对于第一个询问，获得的武器为 1 ，选出一把武器的方案为 (1)
对于第二个询问，没有获得的武器。
对于第三个询问，获得的武器为 2，选出一把武器的方案为 (2)
对于第四个询问，获得的武器为 1,2，选出一把武器的方案为 (1), (2) 两种。

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