#include "towers.h"

#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> H, pos;

void init(int N, std::vector<int> H) {
        ::N=N, ::H=H;

        for(int i=0;i+1<N;) {
                if(H[i]<H[i+1]) {
                        if(pos.empty()|| pos.back()!=i)
                                pos.push_back(i);
                        int j=i;
                        while(j+1<N && H[j]<H[j+1]) j++;
                        i=j;
                } else {
                        int j=i;
                        while(j+1<N && H[j]>H[j+1]) j++;
                        i=j;
                        pos.push_back(i);
                }
        }
}

int max_towers(int L, int R, int D) {
        auto lf=lower_bound(pos.begin(),pos.end(),L);
        auto rg=upper_bound(pos.begin(),pos.end(),R);
        return rg-lf;
}