#include <iostream>
#include<bits/stdc++.h>

using namespace std;

int count(int k , vector<int>& arr){
	int i=0;
	int j=0;
	unordered_map<int,int> mpp;
	int ans=0;
	int n = arr.size();
	
	
	while(j<n){
		mpp[arr[j]]++;
		while(mpp.size()>k){
			mpp[arr[i]]--;
			if(mpp[arr[i]]==0){
				mpp.erase(arr[i]);
			}
			i++;
		}
		ans+=(j-i+1);
	    j++;
	    
	}
	return ans;
	
}


int main() {
	// your code goes here
	int n;
	cin>>n;
	vector<int> arr(n);
	
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	
	int tot = n*(n+1)/2;
	int v=0;

	if(tot%2==0){
		v=tot/2;
	}
	else{
		v=(tot+1)/2;
	}
	
	int low=1;
	int high = n;
	int ans=0;
	
	while(low<=high){
		int mid = (low+high)/2;

		if(count(mid,arr)>=v){
             ans=mid;
             high=mid-1;
             
		}
		else{
			low = mid+1;
		}
	}
	
	cout<<ans<<endl;
	
	
	
	return 0;
}