#line 1 "a.cpp" #pragma region Macros #include using namespace std; template inline bool chmax(T &a, T b) { if(a < b) { a = b; return 1; } return 0; } template inline bool chmin(T &a, T b) { if(a > b) { a = b; return 1; } return 0; } #ifdef DEBUG template ostream &operator<<(ostream &os, const pair &p) { os << '(' << p.first << ',' << p.second << ')'; return os; } template ostream &operator<<(ostream &os, const vector &v) { os << '{'; for(int i = 0; i < (int)v.size(); i++) { if(i) { os << ','; } os << v[i]; } os << '}'; return os; } void debugg() { cerr << endl; } template void debugg(const T &x, const Args &... args) { cerr << " " << x; debugg(args...); } #define debug(...) \ cerr << __LINE__ << " [" << #__VA_ARGS__ << "]: ", debugg(__VA_ARGS__) #define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl #else #define debug(...) (void(0)) #define dump(x) (void(0)) #endif struct Setup { Setup() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } __Setup; using ll = long long; #define ALL(v) (v).begin(), (v).end() #define RALL(v) (v).rbegin(), (v).rend() #define FOR(i, a, b) for(int i = (a); i < int(b); i++) #define REP(i, n) FOR(i, 0, n) const int INF = 1 << 30; const ll LLINF = 1LL << 60; constexpr int MOD = 1000000007; const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, 1, 0, -1}; void Case(int i) { cout << "Case #" << i << ": "; } #pragma endregion Macros #line 1 "/home/siro53/kyo-pro/compro_library/graph/dsu.hpp" struct UnionFind { vector par; UnionFind(int n) : par(n, -1) {} void init(int n) { par.assign(n, -1); } int root(int x) { if(par[x] < 0) return x; else return par[x] = root(par[x]); } bool issame(int x, int y) { return root(x) == root(y); } bool merge(int x, int y) { x = root(x); y = root(y); if(x == y) return false; if(par[x] > par[y]) swap(x, y); // merge technique par[x] += par[y]; par[y] = x; return true; } int size(int x) { return -par[root(x)]; } }; #line 70 "a.cpp" int main() { int N; cin >> N; vector> a(N); REP(i, N) { cin >> a[i].first; a[i].second = i; } sort(ALL(a)); debug(a); set se; UnionFind uf(N); REP(i, N) { if(se.count(a[i].second + 1)) { uf.merge(a[i].second, a[i].second + 1); } se.emplace(a[i].second); } int ans = 0; se.clear(); REP(i, N) { if(se.count(uf.root(i))) continue; ans += uf.size(i) - uf.size(i) / 2; se.insert(uf.root(i)); } cout << ans << endl; }