I dont't think that problem can be solved in o(n) time , however here is an o(nlog(n)) time solution using segment tree or any range query data structure ...

So all you need in this problem is to precount the function f for each index i, f(1,i,a[i]) and f(i,n,a[i]) and store these values in different arrays , a prefix array let's name it L and a suffix array let's name it R .

Now we use segment tree , build it with the suffix array R for each node you store a vector and you only have to merge nodes using a function called merge, you can see an example about it here , now in order to count your answer you only have to answer queries for each index i in [1,n] : how many values in range(i+1,n) that are less than L[i] and add it to the answer , here use lower_bound for each node covering a partial range in (i+1,n) .

That's it , i hope that was clear ..