Выкуси Макс

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <queue>
#include <bitset>
#include <stack>
#include <iostream>
#include <fstream>
#include <cmath>

#define sqr(a) ((a)*(a))
#define odd(a) ((a)&1)
#define foru(i,n) for (int i=0;i<(n);i++)
#define ford(i,n) for (int i=(n)-1;i>=0;i--)
#define forab(i,l,r) for (int i=(l);i<=(r);i++)
#define forabd(i,r,l) for (int i=(r);i>=(l);i--)
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(__X) (int)__X.size()
#define pii pair<int,int>

const double eps=1e-19;
const double PI=acos(-1.0);
const int INF=1000*1000*1000+7;
const int MAXN = 500005;

using namespace std;

int n,l;
long long ans;
vector< pair<long long,int> > a;
//set<int> num, key;
int b[MAXN];
int sumr, suml;
int lev[MAXN];

void merge_sort_with_blackjack_and_bitches(int l, int r)
{
    if ( l==r)
        return;
    int sr = (l+r)/2;
    merge_sort_with_blackjack_and_bitches(l, sr);
    merge_sort_with_blackjack_and_bitches(sr+1, r);
    int i1=l, i2=sr+1;
    for (int i=l; i<=r; i++)
    {
        if ( i2>r || (b[i1] < b[i2] && i1<=sr) )
            lev[i] = b[i1++];
            else
            {
                lev[i] = b[i2++];
        // it's a my magic formula
                ans += sr-i1+1;
            }
    }
    for (int i=l; i<=r; i++)
        b[i] = lev[i];
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    scanf("%d %d", &n, &l);
    int tx;
    long long sum;
    ans=0;
    vector<long long>::iterator it;
    a.clear();
    for (int i=0; i<n; i++)
    {
        scanf("%d", &tx);
        sum = 1ll*l*tx + i +1;
        a.push_back( make_pair(sum, i));
        /*it = upper_bound( all(a), sum);
        if ( it != a.end() )
            ans += a.end() - it;
        if ( it == a.end() )
            a.push_back(sum);
            else a.insert(it, sum);*/
        //printf("\n"); for(int j=0; j<sz(a); j++) printf("%lld ", a[i]); printf("\n");
    }
    stable_sort( all(a));
    for (int i=0; i<n; i++)
        b[i] = a[i].S;
    merge_sort_with_blackjack_and_bitches(0, n-1);
    cout<<ans;
    return 0;
}