Invariant Pairs

The first line contains a single integer N, the size of the array.

The second line contains N space-separated integers, representing the elements of the array a.

Print a single integer representing the total count of such ordered pairs.

A brute-force solution that checks every possible pair (i, j) would have a time complexity of O(N^2) and will be too slow for the given constraints. A more efficient O(N) solution can be achieved by calculating the value a[k] - k for each index k and using a hash map to count the frequencies of these values.

Sample Input 1:

4
2 4 4 5

Sample Output 1:

6

Explanation for Sample 1:

Let's calculate the value a[k] - k for each index k:
  k=0: a[0] - 0 = 2 - 0 = 2
  k=1: a[1] - 1 = 4 - 1 = 3
  k=2: a[2] - 2 = 4 - 2 = 2
  k=3: a[3] - 3 = 5 - 3 = 2
The values are [2, 3, 2, 2]. The value 2 appears k=3 times (at indices 0, 2, 3).
The number of ordered pairs from these 3 indices is 3 * (3 - 1) = 6.
The pairs are: (0, 2), (0, 3), (2, 0), (2, 3), (3, 0), (3, 2).
The value 3 appears once, contributing 1 * (1 - 1) = 0 pairs.
Total count = 6 + 0 = 6.

Sample Input 2:

3
1 2 3

Sample Output 2:

6

Explanation for Sample 2:

Let's calculate a[k] - k:
  k=0: a[0] - 0 = 1 - 0 = 1
  k=1: a[1] - 1 = 2 - 1 = 1
  k=2: a[2] - 2 = 3 - 2 = 1
The value 1 appears k=3 times. The number of ordered pairs is 3 * (3 - 1) = 6.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

1 <= N <= 2 * 10^5
-10^9 <= a[i] <= 10^9

Time limit: 1 sec