#include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define fi first #define sc second #define all(x) (x).begin(), (x).end() #define Bit(x, y) ((x >> y) & 1) #define inpFile(Task) freopen(Task".inp", "r", stdin); #define outFile(Task) freopen(Task".out", "w", stdout); #define submitFile(Task) inpFile(Task); outFile(Task); using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; using ull = unsigned long long; const ll INF = (ll)1e18, MOD1 = (int)1e9 + 7, MOD2 = (int)998244353; template<class X, class Y> void maximize(X &a, const Y &b) { a = (a < b) ? b : a; } template<class X, class Y> void minimize(X &a, const Y &b) { a = (a > b) ? b : a; } template<class T> void add(T& a, T b, T mod) { a += b; if(a >= mod) a -= mod; } template<class T> void sub(T& a, T b, T mod) { a -= b; if(a < 0) a += mod; } const int maxn = (int)1e6 + 8; int n, a[maxn]; vector<int> val; int m, bit[maxn]; void upd(int idx, int valv) { while(idx <= m) { bit[idx] += valv; idx += idx & -idx; } } int get(int idx) { int res = 0; while(idx > 0) { res += bit[idx]; idx -= idx & -idx; } return res; } int kth(int k) { if(k <= 0) return -1; int idx = 0, tmp = 1; while(tmp <= m) tmp <<= 1; for(int i = tmp; i > 0; i >>= 1) { if(idx + i <= m && bit[idx + i] < k) { k -= bit[idx + i]; idx += i; } } if(idx + 1 > m) return -1; return idx + 1; } int getPos1(int pos) { int sum = get(pos - 1); if(get(m) <= sum) return -1; return kth(sum + 1); } int getPos2(int pos) { int sum = get(pos); if(get(m) <= sum) return -1; return kth(sum + 1); } int getIdx(int x) { int l = 0, r = m - 1; while(l <= r) { int mid = (l + r) >> 1; if(val[mid] == x) return mid + 1; if(val[mid] < x) l = mid + 1; else r = mid - 1; } return -1; } signed main() { cin.tie(0)->ios_base::sync_with_stdio(0); cin >> n; a[n + 1] = -INF; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) val.pb(a[i]); val.pb((int)INF); sort(all(val)); val.erase(unique(all(val)), val.end()); m = (int)val.size(); int idx = getIdx((int)INF); upd(idx, 1); int j = 1, ans = 0; for(int i = 2; i <= n + 1; i++) { if(a[i] >= a[i - 1]) continue; while(j < i) { int last = getIdx(a[j]); int pos = getPos2(last); if(pos == -1) pos = idx; while(j < i) { int curr = getIdx(a[j]); int x = getPos1(curr); if(x == -1) break; if(x <= pos) { upd(curr, 1); j++; } else break; } ans++; } } cout << ans; cerr << "\nExecution time: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n"; return 0; }