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
 96
 97
 98
 99
100
101
102
103
104
105
#include <bits/stdc++.h>

using namespace std;

int n, W, res = 0;
int tab[1000006];
int gdzie; // pozycja liczby n w ciagu

void mediana(int b) // mediana elementow przedzialow [b, b], [b-1, b], [b-2, b], ... [0, b]
{
    priority_queue<int> s;                            // stos elemntow mniejszych od aktualnej mediany
    priority_queue<int, vector<int>, greater<int>> g; // stos elemntow mniejszych od aktualnej mediany

    int med = 2 * tab[b]; // zmienna med jest podwojona mediana (unikam dzielenia przez 2)
    s.push(tab[b]);
    int ile = 1; // dlugosc rozpatrywanego przedzialu

    if (W == ile + med) // warunek dobrego przedzialu
        res++;

    /*  At any time we try to make heaps balanced and
        their sizes differ by at-most 1. If heaps are
        balanced,then we declare median as average of
        s.top() and g.top()
        If heaps are unbalanced,then median is defined
        as the top element of heap of larger size  */
    for (int i = b - 1; i >= 0; i--)
    {
        ile++;
        int x = tab[i];

        // case1(left 's' heap has more elements)
        if (s.size() > g.size())
        {
            if (2 * x < med)
            {
                g.push(s.top());
                s.pop();
                s.push(x);
            }
            else
                g.push(x);

            med = s.top() + g.top();
        }

        // case2(both heaps are balanced)
        else if (s.size() == g.size())
        {
            if (2 * x < med)
            {
                s.push(x);
                med = 2 * s.top();
            }
            else
            {
                g.push(x);
                med = 2 * g.top();
            }
        }

        // case3(right side heap has more elements)
        else
        {
            if (2 * x > med)
            {
                s.push(g.top());
                g.pop();
                g.push(x);
            }
            else
                s.push(x);

            med = s.top() + g.top();
        }

        if (W == ile + med)
            res++;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> tab[i];
        if (tab[i] == n)
            gdzie = i;
    }

    W = 2 * n + 1;
    res = 0;

    for (int i = gdzie; i < n; i++)
        mediana(i);

    cout << W << " " << res;

    return 0;
}