#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = long long;
const ll N=2e5+29;
const string br="617283";
ll n,a[N],ans=1e18;
vector<vector<ll>>cur;
void f(ll x){
if(x==n){
ll cnt=0;
set<ll>s;
for(ll i=0;i<cur.size();i++){
ll mn=cur[i].front();
ll mx=cur[i].back();
auto it=s.lower_bound(mx);
if(it==s.begin()){
goto can;
}
--it;
if(mn<*it){
return;
}
can:;
for(ll i:cur[i]){
s.insert(i);
}
}
ans=min(ans,(ll)cur.size());
return;
}
x++;
if(a[x]>=a[x-1]){
cur[cur.size()-1].push_back(a[x]);
f(x);
cur[cur.size()-1].pop_back();
}
cur.push_back({a[x]});
f(x);
cur.pop_back();
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(ll i=1;i<=n;i++)cin>>a[i];
cur.push_back({});
f(0);
cout<<ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |