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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>

using namespace std;
int t[2000000];
int gdzie[2000000];
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>t[i];
        gdzie[t[i]]=i;
    }
    cout<<2*n+1<<" ";
    long long wynik=1;
    int l=gdzie[n];
    int p=gdzie[n];
    int ktory=n-1;
    for(int i=2;i<=n;i++)
    {
        if(i%2==0)
        {
            l=min(l,gdzie[ktory]);
            p=max(p,gdzie[ktory]);
            ktory--;
        }
        if(p-l+1>i)
            continue;
        //cout<<l-1<<" "<<n-p<<"\n";
        if(l-1<n-p)
        {
            //cout<<"jeden "<<l-1<<" "<<i-(p-l+1)<<"\n";
            if(l-1<i-(p-l+1))
            {
                //cout<<"dwa "<<n-p<<" "<<i-(p-l+1)<<"\n";
                if(n-p>=i-(p-l+1))
                    wynik+=l;
                else{
                    int ile=(i-(p-l+1))-(n-p);
                    wynik+=(l-1-ile+1);
                }
            }
            else wynik+=(i-(p-l));
        }
        else{
            //cout<<"trzy "<<n-p<<" "<<i-(p-l+1)<<"\n";
            if(n-p<i-(p-l+1))
            {
                //cout<<"cztery "<<l-1<<" "<<i-(p-l+1)<<"\n";
                if(l-1>=i-(p-l+1))
                    wynik+=(n-p+1);
                else{
                    int ile=(i-(p-l+1))-(l-1);
                    //cout<<"piec "<<ile<<"\n";
                    wynik+=(n-p-ile+1);
                }
            }
            else wynik+=(i-(p-l));
        }
        //cout<<i<<": "<<l<<" "<<p<<" "<<wynik<<"\n";
    }
    cout<<wynik;
    return 0;
}