#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;
}