is it possible ?

This question arose in my mind recently, while working on a similar problem:

Given an integer array A with n integers. R is an array of size n where R[i] denotes the number of distinct j, such that i < j and A[i] ≥ A[j]. Is it possible to calculate R in O(n) time?

The Answer:

This is not possible in the general case. Because, if it was possible, then we could have designed an O(n) sorting algorithm for arbitrary integer arrays in the following way:

Lets assume that it is possible to compute the array R in O(n) time. Note that, in that case, it would also be possible to compute another similar array L of size n, where L[i] denotes the number of distinct j, such that i > j and A[i] ≥ A[j].

Now, L[i]+R[i] is the number of distinct j such that, i ≠ j, and A[j] ≤ A[i]. This tells us, for each i, where to place the number A[i] in the sorted array and sort A in O(n).

Question:

Is it possible to solve the task in O(n) time, if the numbers in A are small positive integers (say ≤ 1000).