Giới thiệu
include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
define PI acos(-1)
typedef complex<double> base;
typedef vector<base> vb;
const int ALPHABET_SIZE = 26;
const int BASE = 31;
const int MAXN = 100000001;
const int INF = 1e9;
const int NBIT = 18;
const int N = 1<<18;
const int MOD = (int)1e9+7;
int di[4] = {-1, 0, 0, 1};
int dj[4] = {0, -1, 1, 0};
void solve() {
int n;
cin >> n;
vector<ll> a(n+2);
a[0] = 0;
for(int i = 1; i <= n; i++) cin >> a[i];
a[n+1] = 0;
ll dp0_prev = 0;
ll prev_t1 = 1, prev_t2 = 1;
ll a_prev = a[0];
for(int i = 1; i <= n+1; i++){
ll ai = a[i];
ll diff = a_prev - ai;
vector<ll> candK = {0};
if(prev_t1 <= a_prev) candK.push_back(prev_t1);
if(prev_t2 <= a_prev) candK.push_back(prev_t2);
sort(candK.begin(), candK.end());
candK.erase(unique(candK.begin(), candK.end()), candK.end());
vector<ll> j = {0, ai};
for(ll k: candK){
if(0 <= k && k <= ai) j.push_back(k);
ll t = k - diff;
if(0 <= t && t <= ai) j.push_back(t);
}
sort(j.begin(), j.end());
j.erase(unique(j.begin(), j.end()), j.end());
int m = j.size();
vector<ll> dpJ(m, LLONG_MAX);
for(int idx = 0; idx < m; idx++){
ll jVal = j[idx];
ll best = LLONG_MAX;
for(ll k: candK){
ll base = dp0_prev;
if(k == prev_t1) base = dp0_prev - 1;
else if(k == prev_t2) base = dp0_prev - 2;
ll cost = 0;
if(k > jVal) cost++;
if(k > diff + jVal) cost++;
best = min(best, base + cost);
}
dpJ[idx] = best;
}
ll dp0_i = LLONG_MAX, dpA = LLONG_MAX;
for(int idx = 0; idx < m; idx++){
if(j[idx] == 0) dp0_i = dpJ[idx];
if(j[idx] == ai) dpA = dpJ[idx];
}
ll t1_i = ai+1, t2_i = ai+1;
for(int idx = 0; idx < m; idx++){
if(dpJ[idx] <= dp0_i - 1){
t1_i = j[idx];
break;
}
}
for(int idx = 0; idx < m; idx++){
if(dpJ[idx] <= dp0_i - 2){
t2_i = j[idx];
break;
}
}
dp0_prev = dp0_i;
prev_t1 = t1_i;
prev_t2 = t2_i;
a_prev = ai;
}
cout << dp0_prev << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int test = 1;
// cin >> test;
while (test--) {
solve();
}
}