deleted

I am assuming the main obstacle to find the cnt[] array in O(n) would be the size of a[i], which is too large to make a count array. So,

If the constraints of a[i] were in the range of 10^6 or so, a simple count array could be created. Let the count array be c[] Then, c[i] = number of times i is present in a. After taking a prefix sum of this array, i.e. c[i] += c[i-1], c[i] would be the number of elements in a not greater than i.

After this, for(int i = 0; i < n; i++) cnt[i] = c[a[i]]; should give you the required answer in O(n)

But, since the constraints of a[i] is large, a simple count array will not work. Instead, you will have to use an unordered_map<long long,int> (details of this at http://www.cplusplus.com/reference/unordered_map/unordered_map/) to do this.

My code for this :

#include<bits/stdc++.h>
using namespace std;
unordered_map<long long,int> ha; //the map used as a count array
long long int a[1000005], cnt[100005];
int main()
{
    int n; cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i],ha[a[i]]++;
    auto j = ha.begin();
    auto i = j++;
    for(; j != ha.end(); i++,j++) (*j).second += (*i).second; //finding prefix sum of the map
    for(int i = 0; i < n; i++) cnt[i] = ha[a[i]];
    for(int i = 0; i < n; i++) cout << cnt[i] << " ";
    return 0;
}

This should be able to find the cnt[] array in O(n) time and O(n) space

If we have the cnt[] array, then we would be able to sort a[] in O(n). And sure we can kind of sort in linear time with counting sort, but that relies on the numbers not being too large and your numbers are pretty large.

So if you manage to calculate this cnt[] array in O(n) time, you would have a O(n) sorting algorithm for arrays of long/int. How come we haven't heard of this magnificent sorting algorithm that basically every standard library should use? Well most likely because it doesn't exist.

So I really think that O(n log n) is your best shot in this problem.

BIT also works

since a[i] is 10^18, but n is just 10^6, there is alot of "unused" values, so we can compress the array like this:

if a={100,5,123456}, make it {2,1,3}

because it doest matter the value, just that it inequality remains unchanged

to do this, copy the array to another array, and sort the array then iterate the original array, use binary search to find its position in the sorted array,

then, after the array is compressed, make a BIT with size n+1, (because the possible largest value in the array is n). and iterate the original array again, assume we are now at indeks i, we do a "point update" in the BIT starting indeks a[i] with 1, we are saying that from range 0 to a[i], we add one more element. so later if we query(i), the way the BIT is set is that it will get the number of elements not greater then i

so, after we are done building the BIT, iterate the array once more, if we are in indeks i, we query a[i] in the bit, and that value is what cnt[i] is...

total complexity: sorting (n log n), n point updates in bit (n log n), so total complexity is O(n log n)

my code: https://ideone.com/Uhkm60

maybe there are simpler approaches, but just sharing mine