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
#include <bits/stdc++.h>

using namespace std;

struct prz{
    int pocz,kon;
};

prz tp[1000000];
int g[1000000],t[1000000];
int n,x;
long long wyn;


int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&t[i]);
        g[t[i]]=i;
    }
    tp[n].pocz=g[n];
    tp[n].kon=g[n];
    for(int i=n-1;i>0;i--){
        tp[i].pocz=min(g[i],tp[i+1].pocz);
        tp[i].kon=max(g[i],tp[i+1].kon);
    }
    for(int i=1;i<=n;i++){
        x=i-(i-1)/2;

        wyn+=max(0,min(min(min(tp[n-x+1].pocz,n-tp[n-x+1].kon+1),i-(tp[n-x+1].kon-tp[n-x+1].pocz)),n-i+1));
        //printf("%d %d %d\n",i,x,wyn);
    }
    printf("%d %lld",2*n+1,wyn);
    return 0;
}