#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
// Function to count subarrays with at most `k` distinct elements
ll count(ll arr[], int n, int k) {
    ll i = 0, j = 0, count = 0;
    unordered_map<ll, ll> freq; // To store the frequency of elements in the current window
 
    while (j < n) {
        // Expand the window by including the current element
        freq[arr[j]]++;
 
        // If the number of distinct elements exceeds `k`, shrink the window
        while (freq.size() > k) {
            freq[arr[i]]--;
            if (freq[arr[i]] == 0) {
                freq.erase(arr[i]);
            }
            i++; // Shrink the window from the left
        }
 
        // Add the number of subarrays ending at `j`
        count += (j - i + 1);
 
        // Move to the next element
        j++;
    }
 
    return count;
}
 
int main() {
    ll n;
    cin >> n;
    ll b[n];
 
    for (ll i = 0; i < n; i++) cin >> b[i];
 
    ll tot = n * (n + 1) / 2; // Total number of subarrays
    ll v = (tot + 1) / 2; // Half of total subarrays, rounded up
 
    // Binary search for the smallest `r` such that count(b, n, r) >= v
    ll left = 1, right = n, r = n;
    while (left <= right) {
        ll mid = (left + right) / 2;
        if (count(b, n, mid) >= v) {
            r = mid; // Potential answer
            right = mid - 1; // Try to find a smaller valid `r`
        } else {
            left = mid + 1; // Increase `r`
        }
    }
 
    cout << r << endl;
    return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGludCBsbDsKCi8vIEZ1bmN0aW9uIHRvIGNvdW50IHN1YmFycmF5cyB3aXRoIGF0IG1vc3QgYGtgIGRpc3RpbmN0IGVsZW1lbnRzCmxsIGNvdW50KGxsIGFycltdLCBpbnQgbiwgaW50IGspIHsKICAgIGxsIGkgPSAwLCBqID0gMCwgY291bnQgPSAwOwogICAgdW5vcmRlcmVkX21hcDxsbCwgbGw+IGZyZXE7IC8vIFRvIHN0b3JlIHRoZSBmcmVxdWVuY3kgb2YgZWxlbWVudHMgaW4gdGhlIGN1cnJlbnQgd2luZG93CgogICAgd2hpbGUgKGogPCBuKSB7CiAgICAgICAgLy8gRXhwYW5kIHRoZSB3aW5kb3cgYnkgaW5jbHVkaW5nIHRoZSBjdXJyZW50IGVsZW1lbnQKICAgICAgICBmcmVxW2FycltqXV0rKzsKCiAgICAgICAgLy8gSWYgdGhlIG51bWJlciBvZiBkaXN0aW5jdCBlbGVtZW50cyBleGNlZWRzIGBrYCwgc2hyaW5rIHRoZSB3aW5kb3cKICAgICAgICB3aGlsZSAoZnJlcS5zaXplKCkgPiBrKSB7CiAgICAgICAgICAgIGZyZXFbYXJyW2ldXS0tOwogICAgICAgICAgICBpZiAoZnJlcVthcnJbaV1dID09IDApIHsKICAgICAgICAgICAgICAgIGZyZXEuZXJhc2UoYXJyW2ldKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBpKys7IC8vIFNocmluayB0aGUgd2luZG93IGZyb20gdGhlIGxlZnQKICAgICAgICB9CgogICAgICAgIC8vIEFkZCB0aGUgbnVtYmVyIG9mIHN1YmFycmF5cyBlbmRpbmcgYXQgYGpgCiAgICAgICAgY291bnQgKz0gKGogLSBpICsgMSk7CgogICAgICAgIC8vIE1vdmUgdG8gdGhlIG5leHQgZWxlbWVudAogICAgICAgIGorKzsKICAgIH0KCiAgICByZXR1cm4gY291bnQ7Cn0KCmludCBtYWluKCkgewogICAgbGwgbjsKICAgIGNpbiA+PiBuOwogICAgbGwgYltuXTsKICAgIAogICAgZm9yIChsbCBpID0gMDsgaSA8IG47IGkrKykgY2luID4+IGJbaV07CiAgICAKICAgIGxsIHRvdCA9IG4gKiAobiArIDEpIC8gMjsgLy8gVG90YWwgbnVtYmVyIG9mIHN1YmFycmF5cwogICAgbGwgdiA9ICh0b3QgKyAxKSAvIDI7IC8vIEhhbGYgb2YgdG90YWwgc3ViYXJyYXlzLCByb3VuZGVkIHVwCiAgICAKICAgIC8vIEJpbmFyeSBzZWFyY2ggZm9yIHRoZSBzbWFsbGVzdCBgcmAgc3VjaCB0aGF0IGNvdW50KGIsIG4sIHIpID49IHYKICAgIGxsIGxlZnQgPSAxLCByaWdodCA9IG4sIHIgPSBuOwogICAgd2hpbGUgKGxlZnQgPD0gcmlnaHQpIHsKICAgICAgICBsbCBtaWQgPSAobGVmdCArIHJpZ2h0KSAvIDI7CiAgICAgICAgaWYgKGNvdW50KGIsIG4sIG1pZCkgPj0gdikgewogICAgICAgICAgICByID0gbWlkOyAvLyBQb3RlbnRpYWwgYW5zd2VyCiAgICAgICAgICAgIHJpZ2h0ID0gbWlkIC0gMTsgLy8gVHJ5IHRvIGZpbmQgYSBzbWFsbGVyIHZhbGlkIGByYAogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIGxlZnQgPSBtaWQgKyAxOyAvLyBJbmNyZWFzZSBgcmAKICAgICAgICB9CiAgICB9CiAgICAKICAgIGNvdXQgPDwgciA8PCBlbmRsOwogICAgcmV0dXJuIDA7Cn0=

NSAgCjUgNSAyIDIgMSA=

5  
5 5 2 2 1