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
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long int ll;

/*

5
1 4 3 5 2


5x - size 1
5x,4x - size 2
5,4x - size 3
5,4x,3x - size 4
5,4,3x - size 5

*/

int calc_range_count(const int n,const int l,const int r,const int size)
{
    const int rl=r-l+1;
    const int extra_needed=size-rl;
    const int min_left=std::max(1,l-extra_needed);
    const int max_left=std::min(l,n-size+1);
    const int count=max_left-min_left+1;
    return count;
}

int main()
{
    int n;
    cin>>n;
	vector<int> a(n+1);
    vector<int> pos(n+1);
    vector<bool> mask(n+1,false);
    mask[n]=true;
    int l,r;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        pos[a[i]]=i;
        if(a[i]==n)
            l=r=i;
    }
    const int func=n*2+1;
    ll result=1;
    int range_size=1;
    for(int num=n-1;num>=(n+1)/2;--num)
    {
        if(!mask[num])
        {
            if(pos[num]>r)
            {
                while(!mask[num])
                    mask[a[++r]]=true;
            }
            else
            {
                while(!mask[num])
                    mask[a[--l]]=true;
            }
        }

        ++range_size;
        if(r-l+1<=range_size)
            result+=calc_range_count(n,l,r,range_size);

        ++range_size;
        if(r-l+1<=range_size)
            result+=calc_range_count(n,l,r,range_size);
    }
    cout<<func<<" "<<result;
    return 0;
}