#include<bits/stdc++.h>

using namespace std;

const int N = 100010;
int arr[N], buff[N];

long long int ans = 0;

void merge_sort(int l, int r)
{
    if (l >= r) return;

    int mid = (l + r) >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);

    int idx = 0, i = l, j = mid + 1;
    for (; i <= mid && j <= r;)
    {
        if (arr[i] <= arr[j]) buff[idx ++] = arr[i ++];
        else {
            buff[idx ++] = arr[j ++];
            ans += mid - i + 1;
        }
    }

    while (i <= mid) buff[idx ++] = arr[i ++];
    while (j <= r) buff[idx ++] = arr[j ++];

    idx = 0;
    for (int i = l; i <= r; ++ i)
    {
        arr[i] = buff[idx ++];
    }

}

int main()
{
    int n; cin >> n;
    for (int i = 0; i < n; ++ i) cin >> arr[i];
    merge_sort(0, n - 1);
    cout << ans;
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

char s[M], p[N];
int ne[N];
int m, n;

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    for (int i = 2, j = 0; i <= n; i ++ )
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }

    for (int i = 1, j = 0; i <= m; i ++ )
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n)
        {
            cout << i - n << " ";
            j = ne[j];
        }
    }

    return 0;
}

#include<bits/stdc++.h>

using namespace std;

string str;
const int N = 100010, P = 131;
typedef unsigned long long  ULL;

// h[i]存的是前i个字符的子数组的哈希值， p[i]存的权值
// 比较时候相当于都把字符串移动到最左边的位置
ULL p[N], h[N];

ULL get(int l, int r)
{
    // 计算的是把l-r的字符串左移到最低位的哈希值
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    int n, m;
    cin >> n >> m >> str;
    str = ' ' + str;

    p[0] = 1;
    for (int i = 1; i <= n; ++ i)
    {
        h[i] = h[i - 1] * P + str[i];
        p[i] = p[i - 1]*P;
    }

    while (m --) {
        int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2;
        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int cur=1, e[N], ne[N];

void add_k(int k, int x)
{
    e[cur] = x; ne[cur] = ne[k]; ne[k] = cur++;
}

void del_k(int k)
{
    ne[k] = ne[ne[k]];
}


int main()
{
    int m; cin >> m;
    while (m--) {
        char op; int k,x;
        cin >> op;
        if (op == 'H') {
            cin >> x;
            add_k(0,x);
        } else if (op == 'I') {
            cin >> k >> x;
            add_k(k,x); 
        } else {
            cin >> k;
            del_k(k);
        }
    }

    for (int j = ne[0]; j ; j = ne[j]) cout << e[j] << ' ';
    cout << endl;
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main()
{
    // wn * 0 + w(n - 1) * 1 + ······ + w0 * (n - 1) 所以让时间最长的先去
    int n; cin >> n;
    vector<int>buff(n);
    for (int i = 0; i < n; ++ i) cin >> buff[i];

    long long ans = 0;
    sort(buff.begin(), buff.end(),greater<int>());

    for (int i = 0; i < n; ++ i) ans += buff[i] * i;

    cout << ans;
    return 0;
}

#include<bits/stdc++.h>

using namespace std;
const int N = 50010;
struct Cow {
    int w, s;
    bool operator<(const Cow&c) const {
        return w + s < c.w + c.s;
    }
}cow[N];

// w1 + w2 + ······w(i - 1) - si
// w1 + w2 + ······w(i) - s(i + 1)

// w1 + w2 + ······w(i - 1) - s(i + 1)
// w1 + w2 + ······w(i - 1) + w(i  + 1) - si


int main()
{
    int n; cin >> n;
    for (int i = 0; i < n; ++ i) cin >> cow[i].w >> cow[i].s;
    sort(cow, cow + n);

    long long sumw = 0, res = -2e9;
    for (int i = 0; i < n; ++ i) {
        res = max(res, sumw - cow[i].s);
        sumw += cow[i].w;
    }
    cout << res;
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

// 假设只有一个点的时：abs的数值为0
// 两个点时：两点中间的任意一个位置都是最小的【包括左右端点】
// 超过两个点取最小的可以扩展

int main()
{   
    int n; cin >> n;
    vector<int>buff(n);
    for (int i = 0; i < n; ++ i) cin >> buff[i];

    sort(buff.begin(), buff.end());

    int p = buff[n/2], ans = 0;
    for (auto v: buff) ans += abs(v - p);
    cout << ans;
    return 0;   
}

#include<bits/stdc++.h>

using namespace std;

priority_queue<int, vector<int>, greater<int>>qwq;

int main()
{
    int n; cin >> n;
    for (int i = 0; i < n; ++ i) {
        int tmp; cin >> tmp;
        qwq.push(tmp);
    }
    int ans = 0;
    while (qwq.size() != 1) {
        int a = qwq.top(); qwq.pop();
        int b = qwq.top(); qwq.pop();
        ans += (a + b);
        qwq.push(a + b);
    }
    cout << ans;
    return 0;
}

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;
char a[N], b[N];
int dp[N][N];

int main()
{
    int len1, len2;
    cin >> len1; scanf("%s", a + 1);
    cin >> len2; scanf("%s", b + 1);

    for (int i = 1; i < len1; ++ i) dp[i][0] = i;
    for (int i = 1; i < len2; ++ i) dp[0][i] = i;

    // 一个三个操作：删除-增加-更改
    // f[i][j] 表示的是a的前i个与b的前j个匹配
    for (int i = 1; i <= len1; ++i) {
        for (int j = 1; j <= len2; ++j) {
            // 如果a[i]与b[j]相等，那就不需要任何操作
            // 删除操作：删除当前的a[i],所以需要的前面一个就是f[i - 1][j]
            // 增加操作：插入之后a[i]与b[j]完全匹配，所以插入的就是b[j] 那填之前a[i]和b[j-1]匹配
            // 修改操作：删除当前的a[i],所以需要的前面一个就是f[i - 1][j - 1]
            if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1];
            else {
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
        }
    }

    cout << dp[len1][len2];
    return 0;
}

```#include[HTML_REMOVED]

using namespace std;

const int N = 1e5 + 7;

// 最大不相交区间数==最少覆盖区间点数
// 覆盖点是全部的区间

struct qwq {
int l, r;
bool operator<(const qwq& q)const {
return r < q.r;
}
}q[N];

int main()
{
int n; cin >> n;

for (int i = 0; i < n; ++ i) cin >> q[i].l >>  q[i].r;
sort(q, q + n);

int ans = 0, ed = -2e9;
// 这边是从最小的遍历，然后用前一个的y与当前的x比较
for (int i = 0; i < n; ++ i) {
    if (q[i].l > ed) {
        ed = q[i].r;
        ans++;
    }
}
cout << ans;
return 0;

}
```