Note: I index the cows as $0\ldots N-1$ rather than $1\ldots N$.

To solve this problem in $\mathcal{O}(N^2)$ time, fix $r$ and count the number of $l$ such that both cows and $l$ and $r$ can be leaders. We do this by iterating over all possible $l$ in decreasing order.

• If $B_l=B_r$, then cow $r$ cannot be a leader in $l\ldots r$. Break.
• Otherwise, if $B_l$ is unique in the range $l\ldots r$, then we increment the answer by one.

My code:

#include<bits/stdc++.h>
using namespace std;
 
int main() {
	int N; cin >> N;
	vector<int> B(N); for (int& b: B) cin >> b;
	int64_t ans = 0;
	for (int r = 0; r < N; ++r) {
		vector<bool> occ(N+1);
		for (int l = r-1; l >= 0; --l) {
			if (B[l] == B[r]) break;
			if (!occ[B[l]]) {
				++ans;
				occ[B[l]] = 1;
			}
		}
	}
	cout << ans << "\n";
}

To solve this problem in $\mathcal{O}(N\log N)$ time, for each $l\le r$ define $\texttt{active}_r[l]$ to equal $1$ if cow $l$'s breed is unique in the range $l\ldots r$, and $0$ otherwise. Also let $\texttt{prev_oc}[j]$ equal the maximum index $i<j$ such that $B_i=B_j$.

For each $r$, we need to sum $\texttt{active}_r[l]$ over all $l\in [\texttt{prev_oc}[r]+1,r-1]$. Note that $\texttt{active}_r[l]=\texttt{active}_{r-1}[l]$ for almost all $l$, aside from for $l=r$ and $l=\texttt{prev_oc}[r]$. Therefore, when transitioning from $r-1$ to $r$, we need to make up to two point updates while allowing range sum queries over $\texttt{active}$. This can be done using a data structure such as a binary indexed tree.

Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class PairsOfCows {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        int[] last = new int[n + 1];
        long answer = 0;
        BinaryIndexTree bit = new BinaryIndexTree(n);
        for (int j = 1; j <= n; j++) {
            int k = Integer.parseInt(tokenizer.nextToken());
            if (last[k] != 0) {
                bit.update(last[k], -1L);
            }
            answer += bit.query(j) - bit.query(last[k]);
            last[k] = j;
            bit.update(j, 1L);
        }
        System.out.println(answer);
    }
 
    static class BinaryIndexTree {
        final int n;
        final long[] bit;
 
        BinaryIndexTree(int n) {
            this.n = n;
            this.bit = new long[n + 1];
        }
 
        void update(int j, long delta) {
            for (; j <= n; j += j & -j) {
                bit[j] += delta;
            }
        }
 
        long query(int j) {
            long res = 0;
            for (; j > 0; j -= j & -j) {
                res += bit[j];
            }
            return res;
        }
    }
}

Alternatively, use an order statistic tree (also mentioned in the link above).

My code:

#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>,
	rb_tree_tag, tree_order_statistics_node_update>;
 
int main() {
	int N; cin >> N;
	Tree<int> T;
	vector<int> last_oc(N+1,-1);
	int64_t ans = 0;
	for (int i = 0; i < N; ++i) {
		int b; cin >> b;
		ans += T.size()-T.order_of_key(last_oc[b]+1);
		T.insert(i);
		if (last_oc[b] != -1) T.erase(last_oc[b]);
		last_oc[b] = i;
	}
	cout << ans << "\n";
}