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
#include<bits/stdc++.h>
using namespace std;
vector<int> V,G;
//vector<bool> color;
int main()
{
    ios_base::sync_with_stdio(0);
    int n;
    long long wynik=0;
    cin>>n;
    V.resize(n+2);
    G.resize(n+1);
    V[0]=-1;
    V[n+1]=-1;
    int idx_n = -1;
    for(int i=1;i<=n;i++)
    {
        cin>>V[i];
        G[V[i]]=i;
    }
    cout<<2*n+1<<" ";
    int l=G[n], r = G[n];
    int ostatni=n;
    for(int i=n;i>0;i--)
    {
        if((n-i)%2 == 1) 
        {
            ostatni--;
            if(G[ostatni] < l) l = G[ostatni];
            if(G[ostatni] > r) r = G[ostatni];
        }
        if(r-l+1 > n-i+1) continue;
        int diff = (n-i+1 - (r-l+1) );
        int dodaj = diff+1-max(0,diff-(l-1)) - max(0,diff-(n-r));
        wynik += dodaj;
        //cout<<i<<" "<<diff<<" "<<l<<" "<<r<<" "<<wynik<<"\n";
    }
    cout<<wynik<<"\n";
    return 0;
}