#include using namespace std; using ll = long long; using PII = std::pair; using PLL = std::pair; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rep2(i, s, n) for (int i = (s); i < (int)(n); i++) class RangeMinorMaxorSumQuery // 0-index { int const intmax = 2147483647; int const intmin = 0; vector sgt; int n; int k; public: RangeMinorMaxorSumQuery(int n1, int f = -1) { if (f == -1) f = intmax; else if (f == 0) f = intmin; int na = 1; int ka = 0; while (na < n1) { na *= 2; ka++; } for (int i = 0; i < 2 * na; i++) sgt.push_back(f); n = na; k = ka; } void update_min(int i, int x) { i += n; sgt[i] = x; while (i > 1) { i /= 2; sgt[i] = min(sgt[2 * i], sgt[2 * i + 1]); } } void update_max(int i, int x) { i += n; sgt[i] = x; while (i > 1) { i /= 2; sgt[i] = max(sgt[2 * i], sgt[2 * i + 1]); } } void update_sum(int i, int x) { i += n; sgt[i] = x; while (i > 1) { i /= 2; sgt[i] = sgt[2 * i] + sgt[2 * i + 1]; } } void add_sum(int i, int x) { i += n; sgt[i] += x; while (i > 1) { i /= 2; sgt[i] = sgt[2 * i] + sgt[2 * i + 1]; } } int getmin(int a, int b, int k = 1, int l = 0, int r = -1) //閉区間 l <= x < r とする { if (r == -1) r = n; if (r <= a || b <= l) return intmax; if (a == l && b == r) return sgt[k]; else return min(getmin(a, min(b, (l + r) / 2), 2 * k, l, (l + r) / 2), getmin(max(a, (l + r) / 2), b, 2 * k + 1, (l + r) / 2, r)); } int getmax(int a, int b, int k = 1, int l = 0, int r = -1) //閉区間 l <= x < r とする { if (r == -1) r = n; if (r <= a || b <= l) return intmin; if (a == l && b == r) return sgt[k]; else return min(getmax(a, min(b, (l + r) / 2), 2 * k, l, (l + r) / 2), getmax(max(a, (l + r) / 2), b, 2 * k + 1, (l + r) / 2, r)); } int getsum(int a, int b, int k = 1, int l = 0, int r = -1) //閉区間 l <= x < r とする { if (r == -1) r = n; if (r <= a || b <= l) return intmin; if (a == l && b == r) return sgt[k]; else return getsum(a, min(b, (l + r) / 2), 2 * k, l, (l + r) / 2) + getsum(max(a, (l + r) / 2), b, 2 * k + 1, (l + r) / 2, r); } int getsegtree(int x) { return sgt[x + sgt.size() / 2]; } void printsegtree() { for (int i = 0; i < 2 * n; i++) { cout << sgt[i] << " "; } cout << endl; } }; int main() { #ifdef DEBUG cout << "DEBUG MODE" << endl; ifstream in("input.txt"); //for debug cin.rdbuf(in.rdbuf()); //for debug #endif const int wmax = 1 << 17; const int w = 1e6; int n, k, x; cin >> n >> k; RangeMinorMaxorSumQuery rsq(w, 0); rep(i, n) { cin >> x; if (x < 0 && rsq.getsegtree(-x) > 0) { rsq.add_sum(-x, -1); } else if (x > 0 && rsq.getsum(x, wmax) < k) { rsq.add_sum(x, 1); } } cout << rsq.getsum(0, wmax) << endl; return 0; }