The conditions given in the Problem Statement is equivalent to that one of the following two holds:

• \(a_i = i\) and \(a_j = j\)
• \(a_i = j\) and \(a_j = i\)

The number of pairs satisfying the former is \(\frac{n(n - 1)}{2}\), where \(n\) is the number of \(k\)’s such that \(a_k = k\).

The number of pairs satisfying the latter can be counted by inspecting each \(i\), because once \(i\) is fixed \(j\) is uniquely determined since \(a_i \neq i\).

Therefore, the problem has been solved in a total of \(O (N)\) time.

Sample code (C++)

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    int same = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i] -= 1;
        if (a[i] == i) {
            same += 1;
        }
    }
    long long ans = (long long)same * (same - 1) / 2;
    for (int i = 0; i < n; ++i) {
        if (a[i] > i and a[a[i]] == i) {
            ans += 1;
        }
    }
    cout << ans << '\n';
    return 0;
}

Sample code (Python)

n = int(input())
a = list(map(int, input().split()))

for i in range(n):
  a[i] -= 1

same = 0
for (i, x) in enumerate(a):
  if i == x:
    same += 1

ans = same * (same - 1) // 2
for (i, j) in enumerate(a):
  if i < j and a[j] == i:
    ans += 1

print(ans)