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

int main()
{
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];

    std::vector<int> suffix_min(n);
    std::vector<int> suffix_max(n);
    std::vector<int> suffix_zachwyty(n);
    std::vector<int> stos_zachwyty;
    suffix_min.back() = suffix_max.back() = a.back();
    stos_zachwyty.push_back(a.back());
    suffix_zachwyty.back() = stos_zachwyty.size();
    for (int i = n - 2; i >= 0; --i)
    {
        suffix_min[i] = std::min(suffix_min[i + 1], a[i]);
        suffix_max[i] = std::max(suffix_max[i + 1], a[i]);
        while (!stos_zachwyty.empty() && stos_zachwyty.back() <= a[i])
            stos_zachwyty.pop_back();
        stos_zachwyty.push_back(a[i]);
        suffix_zachwyty[i] = stos_zachwyty.size();
    }
    
    std::vector<int> prefix_zachwyty(n);
    int prefix_stos_size = 1;
    int prefix_stos_top = a[0];
    prefix_zachwyty[0] = 1;
    for (int i = 1; i < n; ++i)
    {
        if (a[i] > prefix_stos_top)
        {
            ++prefix_stos_size;
            prefix_stos_top = a[i];
        }
        prefix_zachwyty[i] = prefix_stos_size;
    }

    int pow = 1;
    while (pow < n)
        pow *= 2;
    std::vector<int> max_tree(pow * 2, 0);
    for (int i = 0; i < n; ++i)
        max_tree[pow + i] = a[i];
    for (int i = pow - 1; i > 0; --i)
        max_tree[i] = std::max(max_tree[i << 1], max_tree[(i << 1) + 1]);

    int max_zachwyty = 0;
    for (int i = 0; i < n; ++i)
    {
        int zachwyty = 0;
        zachwyty += suffix_zachwyty[i];

        if (i > 0)
        {
            int max = suffix_max[i];

            int left_most_above_max = 1;
            while (left_most_above_max < pow)
            {
                int left = left_most_above_max * 2;
                if (max_tree[left] > max)
                {
                    left_most_above_max = left;
                    continue;
                }
                int right = left + 1;
                if (max_tree[right] > max)
                {
                    left_most_above_max = right;
                    continue;
                }
                break;
            }
            if (left_most_above_max >= pow)
            {
                left_most_above_max -= pow;
                if (left_most_above_max < i)
                {
                    int right_zachwyty = prefix_zachwyty[i - 1] - prefix_zachwyty[left_most_above_max] + 1;
                    zachwyty += right_zachwyty;
                }
            }
        }

        max_zachwyty = std::max(max_zachwyty, zachwyty);
    }

    std::cout << max_zachwyty;
    return 0;
}

/*

4
3 4 1 2


7
1 7 2 3 7 2 9

*/