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
#include <bits/stdc++.h>
#define QED return 0;}
#define main() int main(){
#define ll long long
#define f first
#define s second
using namespace std;

ll n, p, k, res = 1, a, b, c, d, mi;
const ll ts = 1000007;
ll t[ts];
ll ind[ts];

main()
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

    cin >> n;
    cout << n * 2 + 1 << ' ';
    for(int i = 1; i <= n; i++){
        cin >> t[i];
        ind[t[i]] = i;
    }

    p = ind[n];
    k = ind[n];
    for(int i = n - 1; i >= (n + 1) / 2; i--){
        if(ind[i] < p) p = ind[i];
        else if(ind[i] > k) k = ind[i];

        if(k - p + 1 <= 2 * (n - i) + 1){

            a = p - 1; b = n - k; mi = 0;
            if(b > a) swap(a, b);
            c = 2 * (n - i) + 1 - (k - p + 1);
            a = min(a, c);
            b = min(b, c);
            d = c - b;
            mi = a - d + 1;

            res += mi;
            //cout << '\n' << res << ' ';
        }
        if(k - p + 1 <= 2 * (n - i)){

            a = p - 1; b = n - k; mi = 0;
            if(b > a) swap(a, b);
            c = 2 * (n - i) - (k - p + 1);
            a = min(a, c);
            b = min(b, c);
            d = c - b;
            mi = a - d + 1;

            res += mi;
            //cout << res;
        }
        //cout << '\n' << res << ' ' << i << ' ' << p << ' ' << k << '\n';
    }
    cout << res;

QED