楼兰图腾

#include<iostream>
#include<string.h>
using namespace std;

typedef long long ll;
const int N=2e5+10;

int n;
int a[N];
ll tr[N];
ll Greater[N],Lower[N];

int lowbit(int x)
{
    return x&-x;
}

void add(int x,int y)
{
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=y;
}

ll sum(int x)
{
    ll res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}

int main()
{
    scanf("%d",&n);

    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    for(int i=1;i<=n;i++)
    {
        int y=a[i];
        Greater[i]=sum(n)-sum(y);//前i-1个数字里面比y大的数字的个数
        Lower[i]=sum(y-1);//前i-1个数字里面比y小的数字的个数

        add(y,1);//更新
    }
    
    memset(tr,0,sizeof tr);
    
    ll res1=0,res2=0;
    
    for(int i=n;i;i--)
    {
        int y=a[i];
        res1+=Greater[i]*1ll*(sum(n)-sum(y));
//        Greater[i]=sum(n)-sum(y);//n~i个数字里面比y大的数字的个数

//        Lower[i]=sum(y-1);//n~i个数字里面比y小的数字的个数

        res2+=Lower[i]*1ll*sum(y-1);

        add(y,1);//更新
    }
    
    printf("%lld %lld",res1,res2);
    
    return 0;
}