PrimeQuery

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long i64;
int n,ind;
vector<i64> v,numbers;
unordered_map<i64,int> pos;
vector<int> aib;

inline i64 Multiply(i64 a, i64 b, i64 MOD)
{
    i64 res(0);
    while(b)
    {
        if(b&1)
        {
            res+=a;
            if(res>=MOD)
                res-=MOD;
        }
        a+=a;
        if(a>=MOD)
            a-=MOD;
        b>>=1;
    }
    return res;
}

inline i64 Powlog(i64 a,i64 b,i64 MOD)
{
    i64 res(1);
    while(b)
    {
        if(b&1)
            res=Multiply(res,a,MOD);
        a=Multiply(a,a,MOD);
        b>>=1;
    }
    return res;
}

inline bool Prim(i64 n)
{
    if(n<2)
        return false;
    if(n==2||n==3||n==5)
        return true;
    if(n%2==0||n%3==0||n%5==0)
        return false;
    i64 d(n-1);
    while(d%2==0)
        d>>=1;
    for(int i=1;i<=2;++i)
    {
        bool ch(true);
        i64 a=2+rand()%(n-4),temp(d);
        i64 x=Powlog(a,temp,n);
        if(x==1||x==n-1)
            continue;
        while(temp!=n-1)
        {
            x=Multiply(x,x,n);
            temp<<=1;
            if(x==1)
                return false;
            if(x==n-1)
            {
                ch=false;
                break;
            }
        }
        if(ch)
            return false;
    }
    return true;
}

void Update(int pos)
{
    for(int i=pos;i<=ind;i+=i&-i)
        ++aib[i];
}

inline int Query(int pos)
{
    int sum=0;
    for(int i=pos;i>0;i-=i&-i)
        sum+=aib[i];
    return sum;
}

int main()
{
    ios_base::sync_with_stdio(false);
    ifstream f("primequery.in");
    f>>n;
    v=numbers=vector<i64>(n);
    for(int i=0;i<n;++i)
        f>>v[i],numbers[i]=v[i];
    f.close();
    sort(numbers.begin(),numbers.end());
    numbers.erase(unique(numbers.begin(),numbers.end()),numbers.end());
    for(const i64&x:numbers) /// In pos pun indicii vectorului sortat
        pos[x]=++ind;
    aib=vector<int>(ind+1); /// Vectorul care retine arborele indexat binar
    ofstream g("primequery.out");
    for(int i=0;i<n;++i)
    {
        g<<Query(pos[v[i]]-1)<<' ';
        if(Prim(v[i]))
            Update(pos[v[i]]);
    }
    g<<'\n';
    g.close();
    return 0;
}