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

inline int min(const int a, const int b) {return (a < b ? a : b);}
inline int max(const int a, const int b) {return (a > b ? a : b);}

constexpr int MAX_OCEN = 1000000;

int pozycje[MAX_OCEN];

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int liczba_ocen;
    std::cin >> liczba_ocen;

    for(int i = 1; i <= liczba_ocen; ++i)
    {
        int ocena;
        std::cin >> ocena;
        pozycje[ocena-1] = i;
    }

    long long wynik = 1; // Caly ciag
    int l = 0x7FFFFFFF, r = -1;
    for(int i = liczba_ocen-1; i; --i)
    {
        if(pozycje[i] < l) l = pozycje[i];
        if(pozycje[i] > r) r = pozycje[i];
        if((pozycje[i-1] < l || pozycje[i-1] > r) && ((liczba_ocen-i)<<1) > r-l+1 && r-l+1 < liczba_ocen)
        {
            int max_dlugosc = liczba_ocen-i-1-(r-l+1-(liczba_ocen-i));
            int lewe = min(min(l-1, (l > pozycje[i-1] ? l-pozycje[i-1]-1 : 0x7FFFFFFF)), max_dlugosc);
            int prawe = min(min(liczba_ocen-r, (pozycje[i-1] > r ? pozycje[i-1]-r-1 : 0x7FFFFFFF)), max_dlugosc);
            if(lewe+prawe < max_dlugosc) max_dlugosc = lewe+prawe;
            //std::cout << l << ' ' << r << ' ' << lewe << ' ' << prawe << ' ' << max_dlugosc << '\n';
            if(lewe < prawe) {int c = lewe; lewe = prawe; prawe = c;}

            wynik += ((long long)(prawe+1)*(prawe+2)>>1)+(long long)(prawe+1)*(lewe-prawe)+(((long long)prawe*(prawe+1)-(long long)(prawe-(max_dlugosc-lewe))*(prawe-(max_dlugosc-lewe)+1))>>1);
            //std::cout << wynik << '\n';
        }
    }

    std::cout << (liczba_ocen<<1|1) << ' ' << wynik << '\n';

    return 0;
}