The Normal Type

There are a lot of Pokemon who are jealous of the fact that they do NOT have any specialty, they're the... normal type of Pokemon. But, what they fail to realize is that their power is their normalcy, the ability to think, rationalize and then act.

But, they do have additional power... Pokemon like Jigglypuff - which are normal, can figure out if a trainer is real or is a part of Team Rocket. And they need to use their power to a great extent.

In an array, which consists of N elements, A1, A2, ..., AN, if a subarray has the total number of distinct elements as that of the original array, that determines the presence of Team Rocket.

You've to help the normal type Pokemon in figuring out the total number of subarrays having the total number of distinct elements same as that of the original array.

Example:

Input:  n = 5, a = [1,2,2,1,1]
Output: 8

Approach

C++

#include <bits/stdc++.h>
using namespace std;

long long theNormalType(long long n, long long a[])
{
    set<long long> st;
    for (long long i = 0; i < n; i++)
        st.insert(a[i]);
    long long j = 0;
    set<long long> st1;
    map<long long, long long> mp;
    long long cnt = 0;
    for (long long i = 0; i < n; i++)
    {
        j = max(j, i);
        while (j < n && st.size() > st1.size())
        {
            mp[a[j]]++;
            if (mp[a[j]] >= 1)
                st1.insert(a[j]);
            j++;
        }
        if (st.size() == st1.size())
            cnt += n - j + 1;
        mp[a[i]]--;
        if (mp[a[i]] == 0)
            st1.erase(a[i]);
    }
    return cnt;
}
int main()
{

    long long n = 5;

    long long a[n] = {1, 2, 2, 1, 1};

    cout << theNormalType(n, a) << "\n";

    return 0;
}