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
108
109
110
111
112
113
114
115
116
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define YES cout << "YES\n"
#define NO cout << "NO\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef long double ld;

#ifdef LOCAL
#define DTP(x, y)                                    \
    auto operator<<(auto &o, auto a)->decltype(y, o) \
    {                                                \
        o << "(";                                    \
        x;                                           \
        return o << ")";                             \
    }
DTP(o << a.first << ", " << a.second, a.second);
DTP(for (auto i : a) o << i << ", ", all(a));
void dump(auto... x) { ((cerr << x << ", "), ...) << '\n'; }
#define debug(x...) cerr << setw(4) << __LINE__ << ":[" #x "]: ", dump(x)
#else
#define debug(...) 42
#endif

stringstream os;
void testing()
{
    os = stringstream();
    /*
        Here create tests by pushing to os (<<).
    */
    os.seekg(0, ios::beg);
    cin.rdbuf(os.rdbuf());
}

struct Stree
{
    int size;
    vi V;
    Stree(int n)
    {
        size = 1;
        while (size < n)
            size *= 2;
        V.resize(size * 2, 0);
    }
    void put(int i, int val)
    {
        i += size;
        while (i)
        {
            V[i] = max(V[i], val);
            i /= 2;
        }
    }
    int find(int i, int j)
    {
        int ans = 0;
        i += size;
        j += size;
        while (i <= j)
        {
            if (i & 1)
                ans = max(ans, V[i++]);
            if (!(j & 1))
                ans = max(ans, V[j--]);
            i /= 2;
            j /= 2;
        }
        return ans;
    }
};

void solve()
{
    int n;
    cin >> n;
    vi V(n);
    for (auto &a : V)
        cin >> a;
    for (int i = 0; i < n; i++)
        V.push_back(V[i]);
    vector<pii> D(sz(V), {-1, 1});
    for (int i = sz(V) - 2; i >= 0; i--)
    {
        int j = i + 1;
        while (j > 0 && V[i] >= V[j])
            j = D[j].first;
        D[i].first = j;
        if (j > 0)
            D[i].second = D[j].second + 1;
    }
    int ans = 0;
    for (auto &[x, y] : D)
        ans = max(ans, y);
    cout << ans << endl;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int Z = 1;
    // cin >> Z;
    while (Z--)
        solve();
}