1. Count no. of hills in an array a, i.e. # no. of triplets (i,j,k) s.t. i<j<k & a[i]<=a[j]>=a[k] Solution:

#include <bits/stdc++.h>
using namespace std;

#define fastio() ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

#define int long long
#define double long double

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define endl '\n'

#define IN_VEC(v,n) vector<int> v(n); for(auto &i : v) cin >> i;
#define IN_ARR(arr,n) for(int i=0;i<n;i++) cin >> arr[i];

const ll INF = 1e18;
const int MOD = 1e9 + 7;
vi t1;
void update(int pos,int x,int lx,int rx){
    if(lx==rx-1){
        t1[x]+=1ll;
        return;
    }
    int mid=(lx+rx)/2;
    if(pos<mid) update(pos,2*x+1,lx,mid);
    else update(pos,2*x+2,mid,rx);
    t1[x]=t1[2*x+1]+t1[2*x+2];
}
int sum(int x,int lx,int rx,int l,int r){
    if(r<=lx || l>=rx) return 0;
    if(l<=lx && rx<=r) return t1[x];
    int mid=(lx+rx)/2;
    return sum(2*x+1,lx,mid,l,r)+sum(2*x+2,mid,rx,l,r);
}
void solve() {
    // 1. Hills - # (i,j,k) st i<j<k & a[i]<a[j]>a[k]
    int n;
    cin>>n;
    IN_VEC(a,n);
    // compress a st 0<=a[i]<=n-1
    vi rank=a;
    sort(all(rank));
    rank.erase(unique(all(rank)),rank.end());
    for(int i=0;i<n;++i){
        a[i]=lower_bound(all(rank),a[i])-rank.begin();
    }
    // we build two segment trees l,r intialised as 0
    t1.assign(n,0ll);
    vi l(n),r(n);
    for(int i=0;i<n;++i){
        l[i]=sum(0,0,n,0,a[i]);
        update(a[i],0,0,n);
    }
    t1.clear();
    t1.assign(n,0ll);
    for(int i=n-1;i>=0;--i){
        r[i]=sum(0,0,n,a[i]+1,n);
        update(a[i],0,0,n);
    }
    int ans=0;
    for(int i=0;i<n;++i){
        ans += l[i]*r[i];
    }
    cout<<ans<<endl;
}

int32_t main() {
    fastio();
    solve();
    return 0;
}