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

using namespace std;

vector<int> T;
int Size, l;

void Stworz(int n)
{
    if (T.size() != 0)
    {
        for (int i = 0; i < T.size(); ++i)
            T[i] = 0;
        return;
    }
    int p = 1;
    while (p < n)
        p *= 2;
    l = p;
    Size = 2 * p - 1;
    for (int i = 0; i <= Size; ++i)
        T.push_back(0);
}

void Dodaj(int a)
{
    a += l;
    while (a != 0)
    {
        ++T[a];
        a /= 2;
    }
}

int Kty(int k)
{
    int akt = 1;
    while (2 * akt <= Size)
    {
        if (T[2 * akt] >= k)
            akt *= 2;
        else
        {
            k -= T[2 * akt];
            akt = 2 * akt + 1;
        }
    }
    return akt - l;
}

int main()
{
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<int> a(n);
    int ost, przed;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        --a[i];
        if (a[i] == n - 1)
            ost = i;
        if (a[i] == n - 2)
            przed = i;
    }
    int odp = 0;
    for (int i = 0; i <= min(ost, przed); ++i)
    {
        Stworz(n);
        for (int j = i; j < n; ++j)
        {
            Dodaj(a[j]);
            if (j >= max(ost, przed))
            {
                int d = j - i + 1;
                if (d % 2 == 0)
                {
                    if (Kty(d / 2) + Kty(d / 2 + 1) + 2 + d == 2 * n + 1)
                        ++odp;
                }
                else
                {
                    if ((Kty(d / 2 + 1) + 1) * 2 + d == 2 * n + 1)
                        ++odp;
                }
            }
        }
    }
    cout << 2 * n + 1 << " " << odp + 1;
    return 0;
}