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
#include <iostream>
#include <vector>

typedef long long ll;
using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin>>n;
    vector<int> a(n);
    vector<int> idx(n + 1);

    for(int i = 0; i < n; ++i) {
        cin>>a[i];
        idx[a[i]] = i;
    }

    ll total = 0;
    int left = idx[n];
    int right = idx[n];
    for(int i = 0; i < n - 1; ++i) {
        int cur_idx = idx[n - i];
        left = min(left, cur_idx);
        right = max(right, cur_idx);

        int next_idx = idx[n - i - 1];
        if(next_idx > left && next_idx < right) continue; // currently examined interval has next element in it - we'll count it in the next iteration

        int cur_len = right - left + 1;
        int max_addition = i - (cur_len - (i + 1));
        if(max_addition < 0) continue; // too large interval

        int max_left = max(0, left - max_addition);
        int min_right = min(n - 1, right + max_addition);
        if(next_idx < left) max_left = max(max_left, next_idx + 1);
        if(next_idx > right) min_right = min(min_right, next_idx - 1);

        int len_a = left - max_left;
        int len_b = min_right - right;
        if(len_a < len_b) swap(len_a, len_b);

        int first = min(max_addition - len_a + 1, len_b + 1);
        int last = len_b + 1;
        total += (first + last) * (last - first + 1) / 2 + last * (len_a - (last - first + 1) + 1);
    }
    ++total; // the whole input

    int result = n + (n + 2)/2 + (n + 1)/2;

    cout<<result<<' '<<total;
}
/*
5
1 4 3 5 2
~ 11 5

5
1 2 3 4 5
~ 11 5

5
4 1 3 2 5
~ 11 2

5
2 3 4 5 1
~ 11 7

6
1 2 3 4 5 6
~ 13 6

6
4 5 6 1 2 3
~ 13 7

6
4 5 2 1 6 3
~ 13 3
*/