P1223:
//前缀和用处出现A_A
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1000010;
int s[N];
struct water
{
    int a,num;
    bool operator <(const water&t) const
    {
        return a<t.a;
    }
}w[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i].a,w[i].num=i;
    sort(w+1,w+n+1);
    long long int res=0;
    s[0]=0;
    for(int i=1;i<n;i++) s[i]=s[i-1]+w[i].a,res+=s[i];
    for(int i=1;i<=n;i++) cout<<w[i].num<<" ";
    cout<<endl;
    printf("%.2lf\n",res*1.0/n);
    return 0;
}

P1803
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1000010;
struct test
{
    int start,end;
    bool operator<(const test&t)const
    {
        return end<t.end;
    }
}a[N];
int main()
{
    int n;
    cin>>n;
    int res=1;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].start>>a[i].end;
    }
    sort(a+1,a+n+1);
    int l=a[1].start,r=a[1].end;
    int num=1;
    for(int i=2;i<=n;i++)
    {
        if(a[i].start>=a[num].end)
        {
            res++;
            l=a[i].start;
            r=a[i].end;
            num=i;
        }
    }
    cout<<res<<endl;
    return 0;
}


p3817
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=100010;
int a[N];
int main()
{
    int n,x;
    long long ans=0,yy=0;
    cin>>n>>x;
    a[0]=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]+a[i-1]>x) yy=a[i]+a[i-1]-x,ans+=yy,a[i]-=yy;
    }
    cout<<ans<<endl;
    return 0;

}