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
#include <bits/stdc++.h>
using namespace std;
int poz[1000*1000+6];

int oblicz_nieparzyste(int p, int n, int dlugosc, int dlugosc2){
    //cout <<"np"<< p<<" "<<n<<" "<<dlugosc<<" "<<dlugosc2<<"<>";
    int l=max(p-dlugosc,0);
    p=min(n-2*dlugosc2-1,p);
    //cout << p-l+1<<" "<< l <<" "<< p<<endl;
    return p-l+1;
}
int oblicz_parzyste(int p, int n, int dlugosc, int dlugosc2){
    //cout <<"p "<< p<<" "<<n<<" "<<dlugosc<<"<>";
    int l=max(p-dlugosc+1,0);
    p=min(n-2*dlugosc2,p);
    //cout << p-l+1<<" "<< l <<" "<< p<<endl;
    return p-l+1;
}


int main(){
int n;
cin >> n;

for (int i=0; i<n;i++){
    int tmp;
    cin >> tmp;
    poz[tmp]=i;
}
cout << 2*n+1<<" ";
int l=n+1;
int p=0;
long long wynik=0;
for (int i=0;i<=n/2+1;i++){
    //cout << "obecnie:"<<n-i<<endl;
    l=min(poz[n-i],l);
    p=max(poz[n-i],p);
    if (2*i<n){
        wynik += max(0,oblicz_nieparzyste(l,n,2*i-(p-l),i));
        //cout << wynik<<endl;
    }
    if (2*i-1<n){
        wynik += max(0,oblicz_parzyste(l,n,2*i-(p-l),i));
        //cout << wynik<<endl;
    }
}
cout << wynik<<endl;
}