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
79
80
81
82
83
84
85
86
87
88
89
#include <iostream> 
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long ll;

const ll MAXN = 1000010;

ll rl[MAXN];
ll n;

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        rl[x] = i;
    }

    ll l = rl[n], r = rl[n];
    ll cd = 0, wn = 1;
    ll k = 1, nxt;

    for(int i = n-1; 2*(n-i) <= n; i--) {
        nxt = rl[i];
        k = n-i;

        // cout << i << ' '  << nxt << endl;
        if (nxt > r) { 
            r = nxt;
        } else if(nxt < l) {
            l = nxt;
        }
 
        cd = r - l  + 1;

        ll sl = 2*k;
        ll lfs = min(sl - cd, l-1);        
        ll rfs = min(sl - cd, n-r);
        
        ll xsl = sl - cd;

        if (xsl == 0) {
            wn += 1;
        } else if(xsl > 0) {
            if (rfs + lfs >= xsl) {
                wn += rfs + lfs - xsl + 1;
            }
        }
        // ll fs = (2*k) - cd;

        // ll x  = max((lfs + rfs) - fs + 1, 0LL);
        // ll x = (rfs + lfs + cd) - (2*k);
        // wn += x; 

        // cout << k << " " << 2*k << " | " << l << ' ' << r << " | " << xsl << ' ' << cd << " | " << lfs << ' ' << rfs << " | " << wn << endl;

        sl = 2*k+1;

        if (sl > n) {
            break;
        }

        lfs = min(sl - cd, l-1);        
        rfs = min(sl - cd, n-r);
        xsl = sl - cd;
        if (xsl == 0) {
            wn += 1;
        } else if(xsl > 0) {
            if (rfs + lfs >= xsl) {
                wn += rfs + lfs - xsl + 1;
            }
        }

        // fs = (2*k + 1) - cd;

        // x = max((lfs + rfs) - fs + 1, 0LL);
        // x = (rfs + lfs + cd) - (2*k+1);
        // wn += x; 

        // cout << k << " " << 2*k+1 << " | " << l << ' ' << r << " | " << xsl << ' ' << cd << " | " << lfs << ' ' << rfs << " | " << wn << endl;
    }
    cout << (2*n)+ 1 << ' ' << wn << endl;
}