1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;
typedef long long ll;

vector<bool> p;


int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int n; cin >> n;
  vector<int> v(n+1);
  priority_queue<pair<ll,int>, vector<pair<ll,int>>, 
  greater<pair<ll,int>>> PQ;

  p.resize(n+1);
  ll s = 0, min = -INF;
  for (int i = 1; i <= n; ++i) {
    cin >> v[i];
    // find if there is some pref[j] in S s.t. pref[j] <= s
    PQ.push({s, i});
    auto t = PQ.top();
    if (t.second == i && t.first < min) {
      PQ.pop();
    }
    s += v[i];
    min = PQ.top().first;
  }

  ll si = 0;
  for (int i = 1; i <= n; ++i) {
    if (s - si >= 0)
      p[i] = true;
    si += v[i];
  }
  v.clear();

  int m = PQ.size();
  vector<int> pref;
  pref.reserve(m);
  for (int i = 0; i < m; ++i) {
    auto t = PQ.top();
    if (p[t.second])
      pref.push_back(t.second);
    PQ.pop();
  }
  p.clear();
  
  m = pref.size();

  vector<int> lis(m+1, INF);
  lis[0] = -INF;


  for (int i = 0; i < m; ++i) {
    int j = upper_bound(lis.begin(), lis.end(), pref[i]) - lis.begin();
    if (lis[j-1] < pref[i] && pref[i] < lis[j]) {
      lis[j] = pref[i];
    }
  }

  int l = n+1;
  for (int i = 1; i <= m; ++i) {
    if (lis[i] < INF)
     l = i;
  }

  cout << n - l;

}

// 7
// 2 -5 2 4 -1 4 -3

// 5
// 11 6 -7 10 11

// 8
// 2 -5 2 4 -1 4 -3 2