#include<bits/stdc++.h>

 #define L unsigned int

 #define MOD 16777216

 #define lowbit(x) ((x)&(-(x)))

 #define M 200005

 using namespace std;

 L b[M]={},a[M]={},n;

 void add(L x,L k){for(L i=x;i<=n;i+=lowbit(i)) b[i]+=k;}

 L query(L x){L k=; for(L i=x;i;i-=lowbit(i)) k+=b[i]; return k;}

 L solve1(){

     static L r[M]={},j[M]={}; L res=;

     memset(b,,sizeof(b));

     for(L i=n;i;i--){

         r[i]=query(n)-query(a[i]);

         add(a[i],);

     }

     memset(b,,sizeof(b));

     for(L i=;i<=n;i++){

         j[i]=query(a[i]);

         add(a[i],i);

     }

     memset(b,,sizeof(b));

     for(L i=;i<=n;i++){

         L l=query(a[i]),now=;

         now+=1LL*l*(i-);

         now-=1LL*l*(l-)/;

         now-=j[i];

         res+=1LL*now*r[i];

         add(a[i],);

     }

     return res;

 }

 L solve2(){

     static L r[M]={},j[M]={}; L res=;

     memset(b,,sizeof(b));

     for(L i=n;i;i--){

         r[i]=query(n)-query(a[i]);

         add(a[i],);

     }

     memset(b,,sizeof(b));

     for(L i=;i<=n;i++){

         j[i]=query(a[i]);

         add(a[i],a[i]);

     }

     memset(b,,sizeof(b));

     for(L i=;i<=n;i++){

         L l=query(a[i]),now=;

         now+=1LL*l*(a[i]-);

         now-=1LL*l*(l-)/;

         now-=j[i];

         res+=1LL*now*r[i];

         add(a[i],);

     }

     return res;

 }

 L solve3(){

     L res=; memset(b,,sizeof(b));

     for(L i=n;i;i--){

         L hh=query(n)-query(a[i]);

         res+=(1LL*hh*(hh-)*(hh-)/);

         add(a[i],);

     }

     return res;

 }

 L solve4(){

     static L f[M]={};

     for(L i=n;i;i--) f[i]=;

     for(L x=;x<=;x++){

         memset(b,,sizeof(b));

         for(L i=n;i;i--){

             L hh=query(n)-query(a[i]);

             add(a[i],f[i]);

             f[i]=hh;

         }

     }

     L res=; for(L i=;i<=n;i++) res+=f[i];

     return res;

 }

 main(){

     scanf("%u",&n);

     for(L i=;i<=n;i++) scanf("%u",a+i);

     L res1=solve1();//1x2x

     L res2=solve2();//14xx

     L res3=solve3();//1xxx

     L res4=solve4();//

     printf("%u\n",((res1+res2-res3+res4)%MOD+MOD)%MOD);

 }