So for each element $$$a[i]$$$ from $$$i = 1 \rightarrow n$$$

• Lets $$$f(x) = $$$ number of appearance of $$$x$$$ in $$$a[1..i-1]$$$

• Then we have the number of pair $$$(j < i)$$$ satisfy the formula is $$$f(k - a[i])$$$

Then the result will be $$$res = \underset{i = 1}{\overset{n}{\Sigma}} f(k - a[i])$$$

• By the way, this code runs onlinely

map<int, int> M;

ll res = 0;
for (int x : a)
{
    res += M[k - x]; /// The number of pair (j < i) satisfy the formula
    ++M[x];          /// Increase the number of appearance of (x) in array
}

cout << res;

Lets $$$g(k) = \underset{i = 1}{\overset{n}{\Sigma}} f(k - a[i])$$$

Lets $$$cost[k]$$$ is the value $$$g(k + 1) - g(k)$$$ so that we have $$$g(k + 1) = g(k) + cost[k]$$$

Then for each $$$a[i]$$$ ($$$i = 1 \dots n$$$)

• We have to increase all $$$cost[j]$$$ ($$$j = 1 \dots n-1$$$) by $$$f(j - a_i + 1) - f(j - a_i)$$$

• We can do that by some data structures that reduce the complexity down to $$$O(polylog\ n)$$$

Then for each queries $$$k = 1 \dots n$$$

• The result will be $$$g(k)$$$

• And by the transistion $$$g(k) = g(k - 1) + cost[k - 1]$$$ we can calculate next query in $$$O(1)$$$