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
90
91
92
93
94
95
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include<algorithm>
#include<vector>

using namespace std;

#define P 1000000007
#define TAB_SIZE 1001001

    long long  i, n, pocz, kon;
    long long tab[TAB_SIZE];
    long long pos[TAB_SIZE];
    bool spr[TAB_SIZE] = { false };


void Widening(int szukany) {
    while (szukany > kon) {
        kon++;
        spr[tab[kon]] = true;
    }
    while (szukany < pocz) {
        pocz--;
        spr[tab[pocz]] = true;
    }
    return;
}



int main()
{

    std::ios_base::sync_with_stdio(false);


   // cout << "Who called in the fleet?" << '\n';

    cin >> n;

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


    long long int ans = 1;
    long long int minim = n;
    spr[n] = true;

    pocz = pos[n];
    kon = pos[n];
    while (minim > 1) {
        minim--;
        Widening(pos[minim]);
        while (spr[minim - 1] == true) {
            minim--;
        }
        //cout << "pocz=" << pocz << " kon=" << kon << '\n';

        long long  int capacity = kon - pocz + 1;
        long long int br = (2 * (n - minim + 1) - 1) - capacity;



        long long a = min(br, pocz - 1);
        if (pos[minim - 1] < pocz) {
            a = min(a, pocz - pos[minim - 1] - 1);
        }
        
        long long b = std::min(br, n - kon);
        if (pos[minim - 1] > kon) {
            b = min(b, pos[minim - 1] - kon - 1);
        }

        //cout << "capacity=" << capacity << " br=" << br << '\n';

        //cout << "a=" << a << " b=" << b << '\n';

        if (br > a + b) {
            ans += (a + 1) * (b + 1);
        }
        else {
            long long c = a + b - br;
            ans -= ((c*(c-1))/2);
            ans += br + 1 + a * b;
        }
        //cout << "ans=" << ans << " minim=" << minim << '\n';
    }

    cout << ans << '\n';
    return 0;
}