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
100
101
102
103
104
105
#include <bits/stdc++.h>
using namespace std;
const int P=1048576;
const long long INF=(long long)P*P*P;
void imax(int &a, int b){
	a=max(a, b);
}
void imin(int &a, int b){
	a=min(a, b);
}
void lmax(long long &a, long long b){
	a=max(a, b);
}
void lmin(long long &a, long long b){
	a=min(a, b);
}
/*
	WARNING: I'm using strange bracket style!
*/
class bush{
	long long s[P*2+10];
	long long t[P*2+10];
	long long a, b, c;
	void lazy(int u){
		s[u]+=t[u];
		if (u<P)
			t[u*2]+=t[u], t[u*2+1]+=t[u];
		t[u]=0;
	}
	int mid(int low, int high){
		return (low+high)/2;
	}
	long long getValue(int x){
		long long res=0;
		x+=P;
		res+=s[x];
		while (x!=0)
			res+=t[x], x/=2;
		return res;
	}
 	pair <int, long long> goDown(int u=1, int low=0, int high=P-1){
		lazy(u);
		if (u>=P)
			{
			if (s[u]+t[u]<0)
				return {u-P, getValue(u-P)};
			else
				return {u-P+1, getValue(u+1-P)};
			}
		if (s[u*2+1]+t[u*2+1]>=0)
			return goDown(u*2+1, mid(low, high)+1, high);
		else
			return goDown(u*2, low, mid(low, high));
		s[u]=max(s[u*2]+t[u*2], s[u*2+1]+t[u*2+1]);
	}
	void upd(int u=1, int low=0, int high=P-1){
		lazy(u);
		if (low>b || high<a)
			return;
		if (a<=low && high<=b)
			{
			t[u]+=c, lazy(u);
			return;
			}
		upd(u*2, low, mid(low, high));
		upd(u*2+1, mid(low, high)+1, high);
		s[u]=max(s[u*2]+t[u*2], s[u*2+1]+t[u*2+1]);
	}
	public:
	void clear(){
		for (int i=0; i<P*2+5; i++)
			s[i]=-INF;
	};
	pair <int, long long> ask(){
		return goDown();
	}
	void update(int x, int y, long long z){
		a=x, b=y, c=z, upd();
	}
};
bush BUSH;
int n, x;
bool first;
void update(int x){
	pair <int, long long> a=BUSH.ask();
	BUSH.update(0, P-1, x);
	if (a.first!=0 && first)
		BUSH.update(a.first, a.first, -a.second);
	first=true;
}
int main()
	{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	BUSH.clear(), BUSH.update(0, 0, INF);
	cin>>n;
	for (int i=0; i<n; i++)
		cin>>x, update(x);
	if (BUSH.ask().first==0)
		cout<<"-1\n";
	else
		cout<<n-1-(BUSH.ask().first-1)<<"\n";
	return 0;
	}