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

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

输入描述

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

第二行输入 n 个整数 a i ​ （1≤a i ​ ≤1e9 ）表示第 i 个关卡遇到的武器的代号（保证任意两个武器的代号互不相同）。

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

接下来的 m 行，每行三个正整数 L i ​ , R i ​ , k i ​ (1≤L i ​ ≤R i ​ ≤n, 1≤k i ​ ≤4) ，表示需要通过的关卡区间。

输出描述

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

用例输入 1

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

用例输出 1 

1
0
1
2

奉上我的代码

#include <bits/stdc++.h>
using namespace std;
long long n , m;
long long a[1000005];
long long f[1000005];
int main()
{
    cin >> n;
    for(long long i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    cin >> m;
    while(m--)
    {
        long long l , r , k , q = 0;
        cin >> l >> r >> k;
        for(long long i = l;i <= r;i++)
        {
            f[i]++;
            if(f[i] == a[i])
            {
                q++;
            }
        }
        long long ans = 1;
        bool flag = 0;
        for(long long i = q;i >= max(k , q - k + 1);i--)
        {
            ans *= i;
            flag = 1;
        }
        if(!flag)
        {
            cout << 0 << endl;
            continue;
        }
        for(long long i = min(k , q - k);i >= 1;i--)
        {
            ans /= i;
        }
        if(flag)
        {
            cout << ans << endl;
        }
    }
    return 0;
}