#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <bitset>
#include <vector>
#include <stack>
typedef long long llong;
const int MAXN = 1000000 + 10;
const int MAXLOG = 20;
int n;
struct Fenwick
{
int tree[MAXN];
void update(int pos, int val)
{
for (int idx = pos ; idx < MAXN ; idx += idx & (-idx))
{
tree[idx] += val;
}
}
int query(int pos)
{
int res = 0;
for (int idx = pos ; idx > 0 ; idx -= idx & (-idx))
{
res += tree[idx];
}
return res;
}
int findKth(int k)
{
int pos = 0;
for (int log = MAXLOG - 1 ; log >= 0 ; --log)
{
if (pos + (1 << log) < MAXN && tree[pos + (1 << log)] < k)
{
pos += (1 << log);
k -= tree[pos];
}
}
return pos + 1;
}
};
int a[MAXN];
int dp[MAXN];
int prefix[MAXN];
bool endHere[MAXN];
std::stack <int> st;
Fenwick tree;
void solve()
{
for (int i = 1 ; i <= n ; ++i)
{
prefix[i] = prefix[i - 1] + (a[i - 1] > a[i]);
tree.update(a[i], 1);
}
for (int i = n ; i >= 1 ; --i)
{
tree.update(a[i], -1);
int allowedTo = tree.findKth(tree.query(a[i]) + 1);
int l = i, r = n + 1, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (a[mid] <= allowedTo && prefix[mid] - prefix[i] == 0)
{
l = mid;
} else
{
r = mid;
}
}
int min = n;
for (int idx = i ; idx <= l ; ++idx)
{
min = std::min(min, dp[idx + 1]);
}
dp[i] = min + 1;
}
std::cout << dp[1] << '\n';
}
void input()
{
std::cin >> n;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> a[i];
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
/*
8
7 6 8 1 5 2 4 3
7 | 5 7 | 1 4 | 1 2 | 1
1 | 1 |1 2| 4 | 5 7 | 7
7 5 7 1 4 1 2 1
5
7 | 5 7 | 1 5 2 4 3
*/
