1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
int tab[1000010];
pair <int,int> sortab[1000010];
int main()
{
    int a,minpoz,maxpoz,d,w=0,rdl,l,p;
    cin >> a;
    for(int i=1;i<=a;i++)
    {
        cin >> tab[i];
        sortab[i].first=tab[i];
        sortab[i].second=i;
    }
    cout << 2*a+1 << " ";
    sort(sortab+1,sortab+a+1);
    minpoz=sortab[a].second;
    maxpoz=sortab[a].second;
    for(int i=1;i<=a;i++)
    {
        if(i%2==0)
        {
            d=a-(i/2);
            minpoz=min(minpoz,sortab[d].second);
            maxpoz=max(maxpoz,sortab[d].second);
        }
        rdl=i-(maxpoz-minpoz+1);
        if(rdl==0)
            w++;
        if(rdl>0)
        {
            l=min(minpoz-1,rdl);
            p=min(a-maxpoz,rdl);
            w+=l+p-rdl+1;
        }
        ///cout << i << " " << w << " " << minpoz <<" " << maxpoz << " " << rdl << "\n";
    }
    cout << w;
}