Given a sequence A with length n,count how many quadruple (a,b,c,d) satisfies: a≠b≠c≠d,1≤a<b≤n,1≤c<d≤n,Aa<Ab,Ac>Ada≠b≠c≠d,1≤a<b≤n,1≤c<d≤n,Aa<Ab,Ac>Ad.

4

2 4 1 3

4

1 2 3 4

1

0

因为只考虑相对大小关系，所以先将数据离散化，然后用树状数组记录前后比i大或者比i小的元素，求出所有个数，分类讨论重合情况，减去重合的元素

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<sstream>

#include<algorithm>

#include<queue>

#include<vector>

#include<cmath>

#include<map>

#include<stack>

#include<fstream>

#include<set>

#include<memory>

#include<bitset>

#include<string>

#include<functional>

using namespace std;

typedef long long LL;

#define MAXN 500009

LL pre_max[MAXN], pre_min[MAXN], post_max[MAXN], post_min[MAXN];

LL a[MAXN], tmp[MAXN];

LL T[MAXN], n;

LL lowbit(LL x)

{

    return x&(-x);

}

void update(LL x)

{

    while (x <= MAXN)

    {

        T[x] += ;

        x += lowbit(x);

    }

}

LL getsum(LL x)

{

    LL sum = ;

    while (x > )

    {

        sum += T[x];

        x -= lowbit(x);

    }

    return sum;

}

int main()

{

    while (scanf("%lld", &n) != EOF)

    {

        memset(T, , sizeof(T));

        for (LL i = ; i <= n; i++)

            scanf("%lld", &a[i]);

        memcpy(tmp, a, sizeof(a));

        sort(tmp + , tmp + n + );

        LL len = unique(tmp + , tmp + n + ) - tmp;

        for (LL i = ; i <= n; i++)

            a[i] = lower_bound(tmp + , tmp + len + , a[i]) - tmp;

        for (LL i = ; i <= n; i++)

        {

            update(a[i]);

            pre_min[i] = getsum(a[i] - );

            pre_max[i] = i - getsum(a[i]);

        }

        LL sum1, sum2;

        sum1 = sum2 = ;

        for (int i = ; i <= n; i++)

        {

            post_min[i] = getsum(a[i] - ) - pre_min[i];

            post_max[i] = n - getsum(a[i]) - pre_max[i];

            sum1 += post_min[i];

            sum2 += post_max[i];

        }

        LL ans = sum1*sum2;

        for (int i = ; i <= n; i++)

        {

            ans -= pre_min[i] * pre_max[i];

            ans -= pre_min[i] * post_min[i];

            ans -= post_max[i] * pre_max[i];

            ans -= post_max[i] * post_min[i];

        }

        printf("%lld\n", ans);

    }

}