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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>

using namespace std;

vector<long long> sumTree, maxTree;
long long treeSize;

long long pot(long long x){
	long long tmp = 1;
	while(x){
		x/=2ll;
		tmp*=2ll;	
	}	
	return tmp;
}

void add(long long v){
	sumTree[1]+=v;
	maxTree[1]+=v;	
}

void push(long long x){
	sumTree[x*2]+=sumTree[x];	
	maxTree[x*2]+=sumTree[x];	
	sumTree[x*2+1]+=sumTree[x];	
	maxTree[x*2+1]+=sumTree[x];	
	sumTree[x] = 0;
}

long long qur(long long q=0, long long r = treeSize-1, long long pt = 1){
	if(q==r){
		return pt;	
	}	

	long long mid = (q+r)/2;
	push(pt);

	if(maxTree[pt*2+1]>=0){
		return qur(mid+1, r, pt*2+1);	
	}
	if(maxTree[pt*2]>=0){
		return qur(q, mid, pt*2);	
	}
	return -1;
}

void update(long long v, long long a, long long q=0, long long r= treeSize-1, long long pt=1){
	if(q==r){
		sumTree[pt] = v;
		maxTree[pt] = v;	
		return;
	}

	push(pt);
	long long mid = (q+r)/2;
	
	if(a<=mid) update(v, a, q, mid, pt*2);
	else update(v, a, mid+1, r, pt*2+1);
	maxTree[pt] = max(maxTree[pt*2], maxTree[pt*2+1]);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
	long long n; cin>>n;
	
	treeSize = pot(n+1);
	sumTree.resize(treeSize*2+1, -1e18);
	maxTree.resize(treeSize*2+1, -1e18);

	vector<long long> dp(n+1, -1e9);
	vector<long long> dp2(n+1, -1e9);

	maxTree[treeSize] = 0;
	sumTree[treeSize] = 0;
	for(long long i = treeSize-1; i>0; i--) maxTree[i] = max(maxTree[i*2], maxTree[i*2+1]);
	for(long long i = treeSize-1; i>0; i--) sumTree[i] = 0;
	dp[0] = 0;
	for(long long i = 0; i < n; i++){
		long long a; cin>>a;
		long long wsk = qur();
		add(a);
		if(wsk!=-1){
			wsk-=treeSize;
			update(a, wsk+1);
		}
		dp.swap(dp2);
		
	}	

	for(long long i = 1; i < treeSize; i++){
		push(i);	
	}
	for(long long i = treeSize+n; i>=treeSize; i--){
		if(maxTree[i]>=0) {cout<<n-(i-treeSize)<<'\n'; return 0;}	
	}
	
	cout<<-1<<'\n';
	return 0;
}