#include "towers.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Fenwick {
    vector<int> fn;
    int n;

    void init(int m) {
        n = m;
        fn.assign(n + 1, -2);
    }

    void modify(int x, int t) {
        for (++x; x <= n; x += x & -x) {
            fn[x] = max(fn[x], t);
        }
    }

    int sum(int x) {
        int ans = -2;
        for (++x; x > 0; x -= x & -x) {
            ans = max(ans, fn[x]);
        }
        return ans;
    }
};

int N;
vector<int> H, localMax, S, yy;
vector<pair<int, int>> answers;
int mountain = -1;

void init(int N, std::vector<int> H) {
    ::N = N, ::H = H;
    yy = H;
    sort(yy.begin(), yy.end());
    S.resize(N);
    for (int i = 0; i < N; ++i) {
        S[i] = lower_bound(yy.begin(), yy.end(), H[i]) - yy.begin();
    }
    localMax.resize(N);
    for (int i = 1; i + 1 < N; ++i) {
        localMax[i] = H[i] > H[i - 1] && H[i] > H[i + 1];
        localMax[i] += localMax[i - 1];
    }
    int mx = max_element(H.begin(), H.end()) - H.begin();
    if (is_sorted(H.begin(), H.begin() + mx + 1) && is_sorted(H.begin() + mx, H.end(), greater<>())) {
        mountain = mx;
    }
    set<int> stMax, stMin;
    set<pair<int, int>> st;
    for (int i = 1; i + 1 < N; ++i) {
        if (localMax[i] != localMax[i - 1]) {
            stMax.emplace(i);
        }
    }
    vector<int> stt(stMax.begin(), stMax.end());
    for (int k = 0; k <= size(stt); ++k) {
        int l = k == 0 ? 0 : stt[k - 1] + 1;
        int r = k == size(stt) ? N - 1 : stt[k] - 1;
        int mn = min_element(H.begin() + l, H.begin() + r + 1) - H.begin();
        stMin.emplace(mn);
        if (k > 0) {
            st.emplace(H[stt[k - 1]] - H[mn], mn);
        }
        if (k < size(stt)) {
            st.emplace(H[stt[k]] - H[mn], mn);
        }
    }
    stMax.emplace(N), stMax.emplace(-1);
    auto era = [&](int mn) {
        int nxtMx = *stMax.lower_bound(mn);
        int prvMx = *--stMax.lower_bound(mn);
        for (int x : {nxtMx, prvMx}) {
            if (x >= 0 && x < N) {
                st.erase({H[x] - H[mn], mn});
            }
        }
    };
    auto upd = [&](int mn) {
        int nxtMx = *stMax.lower_bound(mn);
        int prvMx = *--stMax.lower_bound(mn);
        for (int x : {nxtMx, prvMx}) {
            if (x >= 0 && x < N) {
                st.insert({H[x] - H[mn], mn});
            }
        }
    };
    while (!st.empty()) {
        auto [diff, mn] = *st.begin();
        answers.push_back({diff - 1, size(stMin)});
        st.erase(st.begin());
        auto it = stMin.find(mn);
        int l = it == stMin.begin() ? -1 : *prev(it);
        int r = next(it) == stMin.end() ? N : *next(it);
        if (l != -1) {
            era(l);
        }
        if (r != N) {
            era(r);
        }
        int nxtMx = *stMax.lower_bound(mn);
        int prvMx = *--stMax.lower_bound(mn);
        for (int x : {nxtMx, prvMx}) {
            if (x >= 0 && x < N) {
                st.erase({H[x] - H[mn], mn});
                if (H[x] - H[mn] == diff) {
                    stMax.erase(x);
                }
            }
        }
        if (l != -1) {
            upd(l);
        }
        if (r != N) {
            upd(r);
        }
        stMin.erase(mn);
    }
    answers.push_back({1e9 + 7, 1});
}

int max_towers(int L, int R, int D) {
    if (L + 1 >= R) {
        return 1;
    }
    if (mountain != -1) {
        return 1 + (mountain > L && mountain < R && H[mountain] - D >= max(H[L], H[R]));
    } else if (D == 1) {
        return localMax[R - 1] - localMax[L] + 1;
    } else if (L == 0 && R == N - 1) {
        int ans = lower_bound(answers.begin(), answers.end(), pair{D, -1})->second;
        return ans;
    } else {
        Fenwick a, b;
        a.init(N), b.init(N);
        for (int i = L; i <= R; ++i) {
            int p1 = upper_bound(yy.begin(), yy.end(), H[i] - D) - yy.begin() - 1;
            int p2 = lower_bound(yy.begin(), yy.end(), H[i] + D) - yy.begin();
            int up = b.sum(p1);
            int down = 1 + max(0, a.sum(N - p2 - 1));
            b.modify(S[i], down);
            a.modify(N - S[i] - 1, up);
        }
        return b.sum(N - 1);
    }
    return 0;
}

answer.code: In function ‘void init(int, std::vector<int>)’:
answer.code:61:26: error: ‘size’ was not declared in this scope
   61 |     for (int k = 0; k <= size(stt); ++k) {
      |                          ^~~~
answer.code:93:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   93 |         auto [diff, mn] = *st.begin();
      |              ^
answer.code:94:38: error: ‘size’ was not declared in this scope
   94 |         answers.push_back({diff - 1, size(stMin)});
      |                                      ^~~~
answer.code:94:26: error: no matching function for call to ‘std::vector<std::pair<int, int> >::push_back(<brace-enclosed initializer list>)’
   94 |         answers.push_back({diff - 1, size(stMin)});
      |         ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/vector:66,
                 from towers.h:1,
                 from answer.code:1:
/usr/include/c++/13/bits/stl_vector.h:1278:7: note: candidate: ‘void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; value_type = std::pair<int, int>]’
 1278 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:1278:35: note:   no known conversion for argument 1 from ‘<brace-enclosed initializer list>’ to ‘const std::vector<std::pair<int, int> >::value_type&’ {aka ‘const std::pair<int, int>&’}
 1278 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_vector.h:1295:7: note: candidate: ‘void std::vector<_Tp, _Alloc>::push_back(value_type&&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; value_type = std::pair<int, int>]’
 1295 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/13/bits/stl_vector.h:1295:30: note:   no known conversion for argument 1 from ‘<brace-enclosed initializer list>’ to ‘std::vector<std::pair<int, int> >::value_type&&’ {aka ‘std::pair<int, int>&&’}
 1295 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
answer.code: In function ‘int max_towers(int, int, int)’:
answer.code:135:67: error: missing template arguments before ‘{’ token
  135 |         int ans = lower_bound(answers.begin(), answers.end(), pair{D, -1})->second;
      |                                                                   ^