#include <bits/stdc++.h> using namespace std; typedef long long ll; pair<int, int> pii; const int maxn = 1e5 + 100; int n, d; int used[maxn]; int f[maxn]; void move_inside(int i); void move_outside(int i); int press_button(); void add(int i){ used[i] = 1; move_inside(i); } void del(int i){ used[i] = 0; move_outside(i); } void clear(){ for(int i = 1; i <= n; i++){ if(used[i]) del(i); } } bool ok(int k){ int x = 0; vector<int> v; for(int i = 0; i < n; i++){ add(i); if(press_button() > k){ x += f[i]; del(i); } } clear(); return x < d; } int min_cardinality(int N){ d = 0; n = N; for(int i = N - 1; i >= 0; i--){ add(i); if(press_button() == 1) f[i] = 1, d++; else del(i); } clear(); int ans = n / d; for(int l = 1, r = n / d - 1; l <= r;){ int mid = (l + r) >> 1; if(!ok(mid)) l = mid + 1; else r = mid - 1, ans = mid; } return ans; }