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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifdef LOCAL
#define debug(...) __VA_ARGS__
#else
#define debug(...) {}
#endif
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int i;
    int n;
    cin>>n;
    cout<<2*n+1<<" ";
    int tab[n+1];
    int gdzie[n+1];
    for (i = 1; i < n+1 ; i++){
        cin>>tab[i];
        gdzie[tab[i]] = i;
    }
    int dl = 2;
    int l = gdzie[n];
    int p = gdzie[n];
    ll wy = 1;
    for (i = n-1 ; i >= n/2 ; i--){
        l = min(l,gdzie[i]);
        p = max(p,gdzie[i]);
        int dist = dl-(p-l+1);
        if (dist >= 0) wy += max(0,min(dist,l-1)-max(0,dist-(n-p))+1);
        //cout<<i<<".5 "<<dl<<" "<<wy<<"\n";
        dl++;
        dist = dl-(p-l+1);
        if (dist >= 0) wy += max(0,min(dist,l-1)-max(0,dist-(n-p))+1);
        //cout<<i<<" "<<dl<<" "<<wy<<"\n";
        dl++;
    }
    cout<<wy<<"\n";
    return 0;
}