【题目描述】：
    在完成了古越州圆盘密码的研究之后，考古学家小布来到了南美大陆的西部。相传很久以前在这片土地上生活着两个部落，一个部落崇拜闪电，另一个部落崇拜高山，他们分别用闪电和山峰的形状作为各自部落的图腾。小布的团队在山洞里发现了一幅巨大的壁画，壁画上被标记出了N个点，经测量发现这N个点的水平位置和竖直位置是两两不同的。小布认为这幅壁画所包含的信息仅与这N个点的相对位置有关，因此不妨设坐标分别为(1, y1) , (2, y2), ..., (n, yn)，其中y1~yn是1~N的一个排列。小布的团队打算研究在这幅壁画中包含着多少个图腾，其中闪电图腾的定义图示如下（图腾的形式只与4个纵坐标值的相对大小排列顺序有关）：

崇拜高山的部落有两个氏族，因而山峰图腾有如下两种形式，左边为A类，右边为B类（同样，图腾的形式也都只与4个纵坐标值的大小排列顺序有关）：

小布的团队希望知道，这N个点中两个部落图腾数目的差值。因此在本题中，你需要帮助小布的团队编写一个程序，计算闪电图腾数目减去山峰图腾数目的值，由于该值可能绝对值较大，本题中只需输出该值对16777216的余数（注意余数必为正值，例如-1对16777216的余数为16777215）。
【题目解法】：
    我表示给我一百年也想不到补集转换，就算告诉我，下面那块给我十天也不一定弄出来TAT...
    首先补集转换：
    f[1324]-f[1243]-f[1432]
    =f[1x2x]-f[1423]-(f[12xx]-f[1234])-(f[14xx]-f[1423])
    =f[1x2x]-f[12xx]+f[1234]-f[14xx]
    =f[1x2x]-(f[1xxx]-f[13xx]-f[14xx])+f[1234]-f[14xx]
    =f[1x2x]-f[1xxx]+f[13xx]+f[1234]
    我们先做一些预处理：
    利用树状数组求出L[i],R[i]分别表示i左边/右边比a[i]小的个数
    利用树状数组求出L1[i]表示i左边j满足a[j]<a[i]的L[j]之和
    利用树状数组求出L2[i]表示i左边j满足a[j]<a[i]的j之和
    利用树状数组求出L3[i]表示i左边j满足a[j]<a[i]的a[j]之和
    然后：
    f[1234]：枚举3的位置，那么右边就是(n-i-R[i])，左边就是L1[i]乘起来即可
    f[1xxx]：枚举1的位置，右边(n-i-R[i])，那么直接C(n-i-R[i],3)即可
    f[1x2x]：比较麻烦，我们枚举2的位置，那么右边就是(n-i-R[i])，左边1x设为(x,y)，要满足x<y且a[y]>a[i]，那么我们考虑容斥，我们直接求出2左边含有1的对就是L[i]*(i-1)，然后我们考虑不合法的有两部分：一部分为y<x，那么就是L2[i]；另一部分就是x<y但是a[y]<a[i]的部分，那么就是C(L[i],2)
    f[13xx]：更麻烦，我们枚举3的位置，那么4的话就有(n-i-R[i])个，然后我们设1和那个2的位置为(x,y)，所以我们再次容斥，求出(x,y)满足x<i,a[x]<a[i],a[y]<a[i]，那么就有L[i]*(a[i]-1)（我来解释一下，首先对于x，方案就是L[i]，然后对于y只有大小限制，显然就有a[i]-1个），但是合法的只有其中的y>i且a[x]<a[y]，然后我们考虑不合法的，也有两部分QAQ：一部分是x<y<i，那么就有C(L[i],2)；第二部分就是a[x]<a[y]但是x>y的部分（我在来解释一下为什么不用减去a[x]>a[y]的部分，因为我们考虑a[x]>a[y]且x>y就是123，那么和上一部分就重合了），这一部分就是L3[i]

    看了题解（orz hzwer）先嘴巴AC一发，然后写啊写
    说实话，代码还是挺好写的就是想的太复杂了...
    一晚上就这么过去了TAT......

UPD：托上面flag的福，我居然在10天内想出来了另一种方法

【另一种解法】：
    首先嘛，补集转换是一样的
    然后f[1234]，f[1xxx]比较简单也是一样的
    我们考虑剩下两个
    f[1x2x]：我们枚举2的位置，那么左边就是(n-i-R[i])，然后我们就转化为求出f[132]的答案（注意那个3是指在前三个里面是最大的），我们考虑随便选去(x,y)满足x<i y<i a[x]<a[y]，那么这一块很好求就是把y的L数组做成树状数组即可，然后我们要减去f[231]，这一块也很好做，我们维护一个数组Lmax[i]，我们从左到右插入a[i]时，我们修改Lmax[1..a[i]]+1（即表示23的对数），然后我们枚举是是查询[a[i]+1..n]的和就好，区间修改区间查询线段树就好
    f[13xx]：我们考虑右边有一个4，他的位置和大小都很好确定，直接枚举3，那么4就是(n-i-R[i])，然后我们考虑那个1和2，设为(x,y)，我们变成求f[132]（⊙▂⊙，貌似可以用上面的方法求？你想多了，我们现在枚举的是3不是2）我们考虑数字对(x,y)满足x<i y>i且a[x]<a[i] a[y]<i的对数，就是L[i]*R[i]，然后我们考虑balabalabalabal...没必要这么复杂，我们直接考虑，令Lmin[i]初始是为L[i]，我们从右到左枚举a[i]是令Lmin[a[i]+1..n]-1，然后查询Lmin[1..a[i]-1]，线段树就好...
【总结】：
    我们发现上面的瓶颈在于f[132]，然后枚举的位置不同，解法也不同
    我们考虑一下原因，假设f[xxxx]有3的是确定的，那么我们考虑如果枚举的那个是最大或者最小的，它是可以直接用线段树求的，否则就要考虑容斥原理了，原因嘛，yy一下吧，我已经傻逼了...

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=200005;
const long long maxmod=16777216;
int n,a[N]; long long bit[N],ans,L[N],R[N];
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
inline void clear()
{
    memset(bit,0,sizeof(bit));
}
inline int lowbit(int x)
{
    return x&(-x);
}
inline void add(int x,long long y)
{
    y=y%maxmod;
    while (x<=n) bit[x]=(bit[x]+y)%maxmod,x+=lowbit(x);
}
inline long long ask(int x)
{
    long long nowans=0;
    while (x>0) nowans=(nowans+bit[x])%maxmod,x-=lowbit(x);
    return nowans;
}
void init()
{
    n=getint(); ans=0;
    for (int i=1; i<=n; i++) a[i]=getint();
    clear(); for (int i=1; i<=n; i++) L[i]=ask(a[i]),add(a[i],1);
    clear(); for (int i=n; i>=1; i--) R[i]=ask(a[i]),add(a[i],1);
}
void solve()
{
    //1234
    clear();
    for (int i=1; i<=n; i++)
    {
        ans=(ans+ask(a[i])*(n-i-R[i])%maxmod)%maxmod;
        add(a[i],L[i]);
    }
    //1xxx
    clear();
    for (int i=1; i<=n; i++)
    {
        long long x=n-i-R[i];
        ans=(ans-x*(x-1)*(x-2)/6)%maxmod;
    }
    //1x2x
    clear();
    for (int i=1; i<=n; i++)
    {
        ans=(ans+(n-i-R[i])*(L[i]*(i-1)%maxmod-ask(a[i])-L[i]*(L[i]-1)/2)%maxmod)%maxmod;
        add(a[i],i);
    }
    //13xx
    clear();
    for (int i=1; i<=n; i++)
    {
        ans=(ans+(n-i-R[i])*(L[i]*(a[i]-1)%maxmod-ask(a[i])-L[i]*(L[i]-1)/2)%maxmod)%maxmod;
        add(a[i],a[i]);
    }
    ans=(ans%maxmod+maxmod)%maxmod;
    printf("%lld\n",ans);
}
int main()
{
    init();
    solve();
    return 0;
}