#include #include #include #include #include #include #include #include #include #include #include #include //#include #define rep(i,n) for (int i=0; i<(int)(n); i++) 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; } typedef long long ll; typedef pair P; using Graph = vector>; //#define INF 10000000 class UnionFind{ public: vector par; UnionFind(int n) : par(n){ for(int i=0; i> n; vector r(n+1); for(int i=1; i> r[i]; } int cnt = 0; int now = 1; while(r[now] != n){ int right = r[now]; int tmp = -1; int next = -1; for(int i=now; i<=right; i++){ if(tmp < r[i]){ next = i; } } now = next; cnt++; } cout << cnt + 1 << endl; return 0; }