https://www.bilibili.com/video/BV1cb411t7AM

//看过上面的视频就很容易看懂我的代码了，这个视频讲的很不错
#include<iostream>
#include<cstring>
using namespace std;
const int N=200002;
int tree[N*3];
int arr[N];
int count[N];
int left_low[N];
int right_low[N];
int left_high[N];
int right_high[N];

void build_tree(int start,int end,int node){
    if(start==end){
        tree[node]=arr[start];
        return ;
    }
    int left_node = node * 2;
    int right_node= node *2+1;
    int mid =start+end;
    mid/=2;
    build_tree(start,mid,left_node);
    build_tree(mid+1,end,right_node);
    tree[node]=tree[left_node]+tree[right_node];
}
void update_tree(int start,int end,int node,int pos,int val){
    if(start==end){
        tree[node]+=val;
    }else{
        int left_node= node* 2;
        int right_node =node *2 +1;
        int mid=(start+end)/2;
        tree[node]+=val;
        if(pos<=mid)update_tree(start,mid,left_node,pos,val);
        else update_tree(mid+1,end,right_node,pos,val);
    }
}
int getsum(int start,int end,int L,int R,int node){
    if(L>R)return 0;
    if(end<L||start>R)return 0;
    if(start>=L&&end<=R)return tree[node];
    int left_node =node*2;
    int right_node=node *2+1;
    int mid=(start+end)/2;
    return (getsum(start,mid,L,R,left_node)+getsum(mid+1,end,L,R,right_node));
}


int main(){
    int n;
    cin >>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    memset(tree,0,sizeof tree);
    for(int i=1;i<=n;i++){
        left_low[i]=getsum(1,n,1,arr[i]-1,1);
        left_high[i]=getsum(1,n,arr[i]+1,n,1);
        update_tree(1,n,1,arr[i],1);

    }
    memset(tree,0,sizeof tree);
    for(int i=n;i>=1;i--){
        right_low[i]=getsum(1,n,1,arr[i]-1,1);
        right_high[i]=getsum(1,n,arr[i]+1,n,1);
        update_tree(1,n,1,arr[i],1);
    }
    long long l=0;
    long long h=0;
    for(int i=1;i<=n;i++){
        h+=(long long)left_low[i]*right_low[i];
        l+=(long long)right_high[i]*left_high[i];
    }

    cout<<l<<' '<<h;


}