This problem is similar to ABC200-C. If you could not solve this problem, this problem may be a hint.

How can we count the number of pairs of integers such that \(A_i \neq A_j\)?
In this problem, \(N \le 3 \times 10^5\), so counting within a naive loop does not finish in time. So, we have to come up with an efficient solution.

Among many possible solutions, we will introduce two of them.

Solution 1

There are \(\frac{N \times (N-1)}{2}\) pairs of integers \((i,j)\) (\(1 \le i < j \le N\)). Now we want to subtract the number of those such that \(A_i=A_j\).

• First, sort the array.
• Then, count how many consecutive same integers are.
  • For example, a sorted sequence \(A'=(2,2,3,4,4,4)\) has two \(2\)s, one \(3\), and four \(3\)s.
• Finally, for every integer \(p\) in the sequence \(A'\), subtract \(\frac{q \times (q-1)}{2}\) from the answer, where \(q\) is the number of \(p\) in the sequence, which is a number of integer pairs \((i,j)\) (\(i < j\)) such that \(A_i=A_j=p\).
  • Note that the equation is also true for \(q=0,1\).

For example, for \(A'=(2,2,3,4,4,4)\), the answer is \(\frac{6 \times 5}{2} - \frac{2 \times 1}{2} - \frac{3 \times 2}{2} = 11\).

Solution 2

• First, for every \(i\) (\(1 \le i \le N\)), sum up the following values \(X\).
  • \(X = N - k\), where \(k\) is the number of terms in \(A\) that is equal to \(A_i\).
• Then, divide the sum by \(2\) and output it.
  • In the original value, every pair of integers \((i,j)\) that satisfies the condition is counted twice.

For example, for \(A=(2,2,3,4,4,4)\), the answer is \(\{(6-2)+(6-2)+(6-1)+(6-3)+(6-3)+(6-3)\} / 2 = 11\).

In order to find “how many terms in \(A\) are equal to \(A_i\)?”, we can either sort the sequence like solution 1, or count them in manner of packet sort with a data structure like map (in C++). (In this problem, be aware of the constraints \(A_i \le 10^9\).)

The time complexity is \(O(N)\) or \(O(N \log N)\), depending on the data structure you use, which is fast enough to solve this problem anyway.

Note that the maximum answer does not fit in a \(32\) bit integer type. (It does fit in a \(64\) bit integer type.)

Sample code in C++ (res1 stores the answer by solution 1, and res2 by solution 2):

#include<bits/stdc++.h>

using namespace std;

int main(){
  long long n;
  cin >> n;
  vector<int> a(n);
  for(auto &nx : a){cin >> nx;}
  long long res1=(n*(n-1)/2),res2=0;
  
  map<int,long long> mp;
  for(int i=0;i<n;i++){mp[a[i]]++;}
  for(int i=0;i<n;i++){res2+=(n-mp[a[i]]);}
  res2/=2;
  
  sort(a.begin(),a.end());
  a.push_back(-1);
  long long cnt=1;
  for(int i=0;i<n;i++){
    if(a[i]!=a[i+1]){
      res1-=((cnt*(cnt-1))/2);
      cnt=1;
    }
    else{cnt++;}
  }
  assert(res1==res2);
  cout << res1 << '\n';
  //cout << res2 << '\n';
}