#include <bits/stdc++.h>
using namespace std;
bool isValid(int mid,vector<int>&nums,int middle){
	int ans=0;
	unordered_map<int,int>mp;
	int n=nums.size();
	int j=0;
	for(int i=0;i<n;i++){
		mp[nums[i]]++;
		while(mp.size()>mid){
			mp[nums[j]]--;
			if(mp[nums[j]]==0)mp.erase(nums[j]);
			j++;
		}
		ans+=(i-j+1);
	}
	return ans>=middle;
}
int main() {
	int n;
	cin>>n;
	vector<int>nums(n);
	for(int i=0;i<n;i++){
		cin>>nums[i];
	}
	int total=((n+1)*n)/2;
	int middle=total/2;
	int st=0;
	int end=n;
	int ans=0;
	while(st<=end){
		int mid=st+(end-st)/2;
		if(isValid(mid,nums,middle)){
			ans=mid;
			end=mid-1;
		}else{
			st=mid+1;
		}
	}
	cout<<ans<<endl;
	return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmJvb2wgaXNWYWxpZChpbnQgbWlkLHZlY3RvcjxpbnQ+Jm51bXMsaW50IG1pZGRsZSl7CglpbnQgYW5zPTA7Cgl1bm9yZGVyZWRfbWFwPGludCxpbnQ+bXA7CglpbnQgbj1udW1zLnNpemUoKTsKCWludCBqPTA7Cglmb3IoaW50IGk9MDtpPG47aSsrKXsKCQltcFtudW1zW2ldXSsrOwoJCXdoaWxlKG1wLnNpemUoKT5taWQpewoJCQltcFtudW1zW2pdXS0tOwoJCQlpZihtcFtudW1zW2pdXT09MCltcC5lcmFzZShudW1zW2pdKTsKCQkJaisrOwoJCX0KCQlhbnMrPShpLWorMSk7Cgl9CglyZXR1cm4gYW5zPj1taWRkbGU7Cn0KaW50IG1haW4oKSB7CglpbnQgbjsKCWNpbj4+bjsKCXZlY3RvcjxpbnQ+bnVtcyhuKTsKCWZvcihpbnQgaT0wO2k8bjtpKyspewoJCWNpbj4+bnVtc1tpXTsKCX0KCWludCB0b3RhbD0oKG4rMSkqbikvMjsKCWludCBtaWRkbGU9dG90YWwvMjsKCWludCBzdD0wOwoJaW50IGVuZD1uOwoJaW50IGFucz0wOwoJd2hpbGUoc3Q8PWVuZCl7CgkJaW50IG1pZD1zdCsoZW5kLXN0KS8yOwoJCWlmKGlzVmFsaWQobWlkLG51bXMsbWlkZGxlKSl7CgkJCWFucz1taWQ7CgkJCWVuZD1taWQtMTsKCQl9ZWxzZXsKCQkJc3Q9bWlkKzE7CgkJfQoJfQoJY291dDw8YW5zPDxlbmRsOwoJcmV0dXJuIDA7Cn0=

NiAxIDUgMiAxIDMgNQo=

6 1 5 2 1 3 5