#include <bits/stdc++.h>
using namespace std;
#define ll long long
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// find_by_order((int)k) returns iterator of the kth element
// order_of_key((T)key) returns the number of elements less than this key
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int& u : a) cin >> u;
map<int, int> st;
for (int i = 0; i < n; i++) st[a[i]] += 1;
a.insert(a.begin(), 0);
auto adjacent = [&](int x, int y) {
if (x == y) return st[x] >= 2;
if (x > y) swap(x, y);
auto iter = st.lower_bound(y);
if (iter == st.begin()) return false;
return prev(iter)->first == x;
};
auto erase_element = [&](int x) {
st[x] -= 1;
if (st[x] == 0) st.erase(x);
};
function<int(int)> solve = [&](int i) {
if (i == 0) return 0;
auto check = [&](int k) {
for (int j = i - 1; j >= k; --j) if (a[j] > a[j + 1])
return false;
vector<pair<int, int>> b = {{a[k], 1}};
for (int j = k + 1; j <= i; j++) if (a[j] == a[j - 1]) b.back().second += 1;
else b.emplace_back(a[j], 1);
if ((int)b.size() == 1) return st[b[0].first] >= b[0].second;
if (st[b[0].first] < b[0].second) return false;
if (st[b.back().first] < b.back().second) return false;
for (int j = 1; j < (int)b.size() - 1; j++) {
auto [x, y] = b[j];
if (st[x] != y) return false;
}
return true;
};
int j = i;
int l = 1, r = i;
if (check(l)) j = l;
else {
while (r - l > 1) {
int m = (l + r) / 2;
if (check(m)) r = m;
else l = m;
}
j = r;
}
for (int k = j; k <= i; k++) erase_element(a[k]);
return 1 + solve(j - 1);
};
cout << solve(n) << "\n";
}
