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

using namespace std;

void fastscan(int &number)
{
    bool negative = false;
    register int c;
    number = 0;
    c = getchar();
    if (c=='-')
    {
        negative = true;
        c = getchar();
    }
    for (; (c>47 && c<58); c=getchar())
        number = number *10 + c - 48;
    if (negative)
        number *= -1;
}

int main()
{
    int n;
    fastscan(n);
    int tab[n] = {}, input;
    for(int i = 0; i < n; i++)
    {
        fastscan(input);
        tab[input - 1] = i; // mapa na pozycje w ciagu

    }

    int pk[n][2];   //  0 - p, 1 - k
    pk[n-1][0] = pk[n-1][1] = tab[n-1];

    // budowa tablicy (p - k)
    if(n%2 == 0)
    {
        for(int i = 0; i < n/2; i++)
        {
            pk[n - 2 - 2 * i][0] = min(pk[n-1-2*i][0],tab[n-i-2]);
            pk[n - 2 - 2 * i][1] = max(pk[n-1-2*i][1],tab[n-i-2]);

            pk[n - 2 - 2 * i-1][0] = pk[n - 2 - 2 * i][0];
            pk[n - 2 - 2 * i-1][1] = pk[n - 2 - 2 * i][1];
        }
        pk[0][0] = min(pk[1][0], tab[n/2 - 1]);
        pk[0][1] = max(pk[1][1], tab[n/2 - 1]);
    }
    else
    {
        for(int i = 0; i < n/2; i++)
        {
            pk[n - 2 - 2 * i][0] = min(pk[n-1-2*i][0],tab[n-i-2]);
            pk[n - 2 - 2 * i][1] = max(pk[n-1-2*i][1],tab[n-i-2]);

            pk[n - 2 - 2 * i-1][0] = pk[n - 2 - 2 * i][0];
            pk[n - 2 - 2 * i-1][1] = pk[n - 2 - 2 * i][1];
        }
    }

    //test
    /*cout << "Mapa:\t";
    for(int i = 0; i < n; i++)
        cout << tab[i]+1 << " ";
    cout<<endl;
    cout<<"PK:\t";
    for(int i = 0; i < n; i++)
        cout<<pk[i][0]+1 << " " <<pk[i][1]+1<<"   ";
    cout<<endl;*/
    
    int zapas, l, p;
    long long cnt = 1;
    for(int i = n - 2; i >= 0; i--)
    {
        zapas = n - i - (pk[i][1] - pk[i][0] + 1);
        //cout << zapas << " " << n - i << "    ";
        if(zapas == 0)
            cnt++;
        if(zapas > 0)
        {
            l = min(pk[i][0], zapas);
            p = min(n - pk[i][1] - 1, zapas);
            cnt += l + p - zapas + 1;
        }
    }

    cout << 2*n + 1 << " " << cnt;
}