#include<bits/stdc++.h>

using namespace std;   

#define forn(i, n) for(int i = 0; i < int(n); i++)
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)

const long long INF64 = 1e18;

int n;
vector<int> a;

bool read()
{
	if (!(cin >> n))
		return false;
	a.resize(n);
	forn(i, n) cin >> a[i];
	return true;
}

vector<int> f;

void upd(int x, int val){
	for (int i = x; i < int(f.size()); i |= i + 1){
		f[i] += val;
	}
}

int get(int x){
	int res = 0;
	for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
		res += f[i];
	return res;
}

int get(int l, int r){ // inclusive
	if (l <= r) return get(r - 1) - get(l - 1);
	return get(l) + (get(int(f.size()) - 1) - get(r));
}

int odist(int i, int j){
	return (j - i + n) % n;
}

struct vset{
	multiset<long long> a;
	int add;
	
	long long get(){
		if (a.empty()) return INF64;
		return *a.begin() + add;
	}
	
	void insert(long long val){
		a.insert(val - add);
	}
	
	void erase(long long val){
		a.erase(a.find(val - add));
	}
	
	void inc(int x){
		add += x;
	}
	
	vset(){
		add = 0;
	}
};

void solve()
{
	a.insert(a.begin(), int(1e9) + 5);
	++n;
	f.assign(n, 0);
	forn(i, n) upd(i, 1);
	
	vector<int> xs = a;
	sort(xs.begin(), xs.end());
	xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
	for (int &x : a) x = xs.end() - lower_bound(xs.begin(), xs.end(), x) - 1;
	int k = xs.size();
	vector<vector<int>> pos(k);
	forn(i, k) pos[a[i]].push_back(i);
	
	vector<long long> dp(n, INF64);
	dp[0] = 0;
	upd(0, -1);
	fore(x, 1, k){
		int c = pos[x].size();
		int j = 0;
		vector<vector<int>> prv(c);
		for (int pj : pos[x - 1]){
			while (odist(pos[x][j], pj) > odist(pos[x][(j + 1) % c], pj))
				j = (j + 1) % c;
			prv[j].push_back(pj);
		}
		if (c == 1){
			for (int j : pos[x - 1]){
				dp[pos[x][0]] = min(dp[pos[x][0]], dp[j] + get(j, pos[x][0]));
				dp[pos[x][0]] = min(dp[pos[x][0]], dp[j] + get(pos[x][0], j) + 1);
			}
		}
		else{
			{
				vset cur;
				for (int j : pos[x - 1]) if (!binary_search(prv[0].begin(), prv[0].end(), j))
					cur.insert(dp[j] + get(pos[x][1], j));
				forn(i, c){
					int ni = (i + 1) % c;
					dp[pos[x][i]] = cur.get() + get(pos[x][ni], pos[x][i]) - 1;
					for (int j : prv[i]){
						dp[pos[x][i]] = min(dp[pos[x][i]], dp[j] + get(pos[x][ni], j) + get(pos[x][ni], pos[x][i]) - 1);
					}
					for (int j : prv[ni]){
						cur.erase(dp[j] + get(pos[x][ni], j));
					}
					cur.inc(-2 * (get(pos[x][i], pos[x][ni]) - 1));
					for (int j : prv[i]){
						cur.insert(dp[j] + get(pos[x][(i + 2) % c], j));
					}
				}
			}
			{
				auto get2 = [&](int l, int r){
					if (l <= r)
						return int(lower_bound(pos[x].begin(), pos[x].end(), r + 1) - lower_bound(pos[x].begin(), pos[x].end(), l));
					int res = lower_bound(pos[x].begin(), pos[x].end(), l + 1) - pos[x].begin();
					res += pos[x].end() - lower_bound(pos[x].begin(), pos[x].end(), r);
					return res;
				};
				vset cur;
				for (int j : pos[x - 1]) if (!binary_search(prv.back().begin(), prv.back().end(), j))
					cur.insert(dp[j] + get(j, pos[x].back()) + get2(pos[x][0], j) - 1);
				forn(i, c){
					int pi = (i - 1 + c) % c;
					dp[pos[x][i]] = cur.get() + get(pos[x][i], pos[x][pi]) - 1;
					for (int j : prv[pi]){
						dp[pos[x][i]] = min(dp[pos[x][i]], dp[j] + get(j, pos[x][pi]) + get2(pos[x][i], j) - 1 + get(pos[x][i], pos[x][pi]) - 1);
					}
					for (int j : prv[i]){
						cur.erase(dp[j] + get(j, pos[x][pi]) + get2(pos[x][i], j) - 1);
					}
					cur.inc(2 * (get(pos[x][pi], pos[x][i]) - 1));
					for (int j : prv[pi]){
						cur.insert(dp[j] + get(j, pos[x][i]) + get2(pos[x][(i + 1) % c], j) - 1);
					}
				}
			}
		}
		for (int i : pos[x]) cerr << i << " " << dp[i] << endl;
		for (int j : pos[x]){
			upd(j, -1);
		}
	}
	long long ans = INF64;
	for (int x : pos[k - 1]) ans = min(ans, dp[x]);
	cout << ans << '\n';
}

int main()
{
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	forn(i, t)
	{
	 	read();
		solve();
	}
}