#include <bits/stdc++.h>
using namespace std;
using lint = long long;
struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)

// Z algorithm (length of longest common prefix for s[0:N] & s[i:N] for each i)
// Complexity: O(N)
// <http://snuke.hatenablog.com/entry/2014/12/03/214243>
template <typename T> std::vector<int> z_algorithm(const std::vector<T> &s) {
    const int N = s.size();
    if (N == 0) return {};
    std::vector<int> ans(N);
    ans[0] = N;
    int i = 1, j = 0;
    while (i < N) {
        while (i + j < N and s[j] == s[i + j]) ++j;
        ans[i] = j;
        if (!j) {
            ++i;
            continue;
        }
        int k = 1;
        while (i + k < N and k + ans[k] < j) ans[i + k] = ans[k], ++k;
        i += k;
        j -= k;
    }
    return ans;
}

std::vector<int> z_algorithm(const std::string &s) {
    const int N = int(s.size());
    std::vector<int> v(N);
    for (int i = 0; i < N; i++) v[i] = s[i];
    return z_algorithm(v);
}

int N;
string T;

lint solve(lint n)
{
    string S = T;
    S += '_';
    REP(_, n) S += "110";

    vector<int> z = z_algorithm(S);
    lint ret = 0;
    FOR(i, T.size() + 1, S.size()) ret += (z[i] == N);
    return ret;
}

int main()
{
    cin >> N >> T;
    lint A = 1000000;
    lint s1 = solve(A), s2 = solve(A * 2);
    lint ret = s1 + (10000000000LL - A) / A * (s2 - s1);
    cout << ret << '\n';
}

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

#define SORT(c) sort((c).begin(), (c).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
#define ANS(ans) cout << (ans) << endl;
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
typedef vector<int> VI;
typedef pair<int, int> P;

void print() { cout << endl; }

template <class Head, class... Tail> void print(Head &&head, Tail &&...tail) {
    cout << head;
    if (sizeof...(tail) != 0)
        cout << " ";
    print(forward<Tail>(tail)...);
}

template <class T> void print(vector<T> &vec) {
    for (auto &a : vec) {
        cout << a;
        if (&a != &vec.back())
        cout << " ";
    }
    cout << endl;
}

template <class T> void print(vector<vector<T>> &df) {
    for (auto &vec : df) {
        print(vec);
    }
}

// repetition
//------------------------------------------
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define REP(i, n) for (long long i = 0; i < (n); ++i)

int main() {
    ll n;
    cin >> n;

    VI v(n);
    REP(i,n){
        cin>>v[i];
    }

    ll ans;
    ans = n*(n-1)/2;
    // print(ans);

    SORT(v);

    ll prev_key;
    ll prev_count=1;
    REP(i,n){
        if(i==0){
            prev_key=v[i];
            prev_count=1;
            continue;
        }

        if(v[i]==prev_key){
            prev_count++;
        } else {
            ans -= prev_count * (prev_count - 1) / 2;
            // print(prev_key,prev_count);
            // print(ans);
            prev_key = v[i];
            prev_count = 1;
        }
    }

    ans-=prev_count*(prev_count-1)/2;

    ANS(ans);
    
    return 0;
}
