#include <bits/stdc++.h>
#define ll long long
#define pi std::pair<int, int>
#define pll std::pair<ll, ll>
#define vi std::vector<int>
#define vll std::vector<ll>
#define vpi std::vector<pi>
#define vpll std::vector<pll>
#define si std::set<int>
void solve() {
int n, max = 1;
std::cin >> n;
vi v(n);
for(auto& el : v)
std::cin >> el;
v.insert(v.end(), v.begin(), v.end());
std::set<pi> s;
vi tab(v.size(), 1e9), ans(v.size(), 1);
for(int i = 0; i < v.size(); i++) {
while(!s.empty() && v[i] > (*s.begin()).first) {
tab[(*s.begin()).second] = i;
s.erase(s.begin());
}
s.insert({v[i], i});
}
for(int i = v.size() - 1; i >= 0; i--)
if(tab[i] != 1e9) {
ans[i] = ans[tab[i]] + 1;
max = std::max(max, ans[i]);
}
std::cout << max << '\n';
}
int main() {
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
int t = 1;
//std::cin >> t;
while(t--) {
solve();
}
}
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 | #include <bits/stdc++.h> #define ll long long #define pi std::pair<int, int> #define pll std::pair<ll, ll> #define vi std::vector<int> #define vll std::vector<ll> #define vpi std::vector<pi> #define vpll std::vector<pll> #define si std::set<int> void solve() { int n, max = 1; std::cin >> n; vi v(n); for(auto& el : v) std::cin >> el; v.insert(v.end(), v.begin(), v.end()); std::set<pi> s; vi tab(v.size(), 1e9), ans(v.size(), 1); for(int i = 0; i < v.size(); i++) { while(!s.empty() && v[i] > (*s.begin()).first) { tab[(*s.begin()).second] = i; s.erase(s.begin()); } s.insert({v[i], i}); } for(int i = v.size() - 1; i >= 0; i--) if(tab[i] != 1e9) { ans[i] = ans[tab[i]] + 1; max = std::max(max, ans[i]); } std::cout << max << '\n'; } int main() { std::ios_base::sync_with_stdio(0); std::cin.tie(0); int t = 1; //std::cin >> t; while(t--) { solve(); } } |
English