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
#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // Odłączenie synchronizacji strumieni dla maksymalnej prędkości wczytywania
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    // Tworzymy podwojoną tablicę od razu
    vector<int> a(2 * n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i + n] = a[i]; // Kopiowanie elementu do drugiej połowy
    }

    // Stos monotoniczny przechowujący indeksy
    vector<int> st;
    st.reserve(2 * n);

    // Tablica przechowująca liczbę zachwytów (rekordów) dla ciągu zaczynającego się w i
    vector<int> depth(2 * n, 1);
    int max_delights = 0;

    // Przechodzimy tablicę od tyłu, by budować ścieżki "Next Greater Element"
    for (int i = 2 * n - 1; i >= 0; --i) {
        // Usuwamy ze stosu wszystkie perły, które nie są ostro większe
        while (!st.empty() && a[st.back()] <= a[i]) {
            st.pop_back();
        }

        // Jeśli stos nie jest pusty, to na górze stosu leży indeks następnej, większej perły
        if (!st.empty()) {
            depth[i] = 1 + depth[st.back()];
        }

        st.push_back(i);

        // Maksymalizujemy wynik tylko dla pierwszych N możliwych początków naszyjnika
        if (i < n) {
            if (depth[i] > max_delights) {
                max_delights = depth[i];
            }
        }
    }

    // Wypisujemy ostateczny, optymalny wynik
    cout << max_delights << "\n";

    return 0;
}