This problem is same as the previous one, but has larger constraints.

Shiro's just moved to the new house. She wants to invite all friends of her to the house so they can play monopoly. However, her house is too small, so she can only invite one friend at a time.

For each of the $n$ days since the day Shiro moved to the new house, there will be exactly one cat coming to the Shiro's house. The cat coming in the $i$-th day has a ribbon with color $u_i$. Shiro wants to know the largest number $x$, such that if we consider the streak of the first $x$ days, it is possible to remove exactly one day from this streak so that every ribbon color that has appeared among the remaining $x - 1$ will have the same number of occurrences.

For example, consider the following sequence of $u_i$: $[2, 2, 1, 1, 5, 4, 4, 5]$. Then $x = 7$ makes a streak, since if we remove the leftmost $u_i = 5$, each ribbon color will appear exactly twice in the prefix of $x - 1$ days. Note that $x = 8$ doesn't form a streak, since you must remove exactly one day. 

Since Shiro is just a cat, she is not very good at counting and needs your help finding the longest streak.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the total number of days.

The second line contains $n$ integers $u_1, u_2, \ldots, u_n$ ($1 \leq u_i \leq 10^5$) — the colors of the ribbons the cats wear. 


-----Output-----

Print a single integer $x$ — the largest possible streak of days.


-----Examples-----
Input
13
1 1 1 2 2 2 3 3 3 4 4 4 5

Output
13
Input
5
10 100 20 200 1

Output
5
Input
1
100000

Output
1
Input
7
3 2 1 1 4 5 1

Output
6
Input
6
1 1 1 2 2 2

Output
5


-----Note-----

In the first example, we can choose the longest streak of $13$ days, since upon removing the last day out of the streak, all of the remaining colors $1$, $2$, $3$, and $4$ will have the same number of occurrences of $3$. Note that the streak can also be $10$ days (by removing the $10$-th day from this streak) but we are interested in the longest streak.

In the fourth example, if we take the streak of the first $6$ days, we can remove the third day from this streak then all of the remaining colors $1$, $2$, $3$, $4$ and $5$ will occur exactly once.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Data structures

Implementation


Solutions:
n = int(input())
u = list(map(int, input().split()))
cnts = [0 for _ in range(10 ** 5 + 1)]
cntcnt = [10 ** 5 + 1] + [0 for _ in range(10 ** 5)]
b = 1
for i in range(n):
	cnts[u[i]] += 1
	cntcnt[cnts[u[i]] - 1] -= 1
	cntcnt[cnts[u[i]]] += 1
	nz = 10 ** 5 + 1 - cntcnt[0]
	j = i + 1
	if nz == 1:
		b = j
		continue
	if j % nz == 1:
		c = j // nz
		if cntcnt[c] + 1 == nz:
			b = j
			continue
	if cntcnt[1] and (j - 1) % (nz - 1) == 0 and (cntcnt[(j - 1) // (nz - 1)] == nz - 1 + (j == nz)):
		b = j
print(b)


n = int(input())
u = [int(s) for s in input().split()]
a = [0 for i in range(100000)]
im = 0
d = dict()
for i in range(n):
	auiold = a[u[i] - 1]
	if auiold != 0:
		d[auiold] -= 1
		if d[auiold] == 0:
			d.pop(auiold)
	a[u[i] - 1] += 1
	auinew = a[u[i] - 1]
	d[auinew] = d.setdefault(auinew, 0) + 1
	if len(d.keys()) == 1 and 1 in d.keys():
		im = i
	elif len(d.keys()) == 1 and len(d.values()) == 1 and (1 in d.values()):
		im = i
	elif len(d.keys()) == 2 and 1 in d.keys() and (d[1] == 1):
		im = i
	elif len(d.keys()) == 2 and max(d.keys()) == min(d.keys()) + 1 and (d[max(d.keys())] == 1):
		im = i
print(im + 1)


n = int(input())
a = list(map(int, input().split()))
if n == 1 or n == 2:
	print(n)
	return
notpar = 0
occ = [0 for i in range(10 ** 5 + 1)]
base = 1
gotone = False
leader = -1
leadby = 0
best = 0
occ[a[0]] += 1
cnt = 1
at1 = 1
for i in range(1, n):
	occ[a[i]] += 1
	if occ[a[i]] == 1:
		notpar += 1
		at1 += 1
		cnt += 1
	elif occ[a[i]] == 2:
		at1 -= 1
	if occ[a[i]] == base:
		notpar -= 1
	elif occ[a[i]] > base:
		if gotone:
			if a[i] != leader:
				base += 1
				notpar = cnt - 2
				leadby -= 1
				if leadby == 0:
					gotone = False
					leader = -1
			else:
				leadby += 1
		else:
			gotone = True
			leader = a[i]
			leadby = 1
	if notpar == 0 and (leadby == 1 or (leadby == 0 and base == 1)) or (notpar == 1 and leadby == 0 and (at1 > 0)):
		best = i + 1
	if cnt == 1:
		best = i + 1
print(best)


from collections import defaultdict
n = int(input())
u = list(map(int, input().split()))
a = [0] * (10 ** 5 + 1)
b = [0] * (10 ** 5 + 1)
mx = 0
best = 1
for (i, collar) in enumerate(u, 1):
	b[a[collar]] = max(0, b[a[collar]] - 1)
	a[collar] += 1
	b[a[collar]] += 1
	mx = max(mx, a[collar])
	if b[1] == i:
		best = i
	elif b[i] == 1:
		best = i
	elif b[1] == 1 and mx * b[mx] == i - 1:
		best = i
	elif b[mx - 1] * (mx - 1) == i - mx and b[mx] == 1:
		best = i
print(best)


from random import random
from collections import defaultdict
import math
import re
import fractions
N = int(input())
A = list(map(int, input().split(' ')))
arr = [0] * (10 ** 5 + 1)
existing = set()
for a in A:
	arr[a] += 1
	existing.add(a)
accumulate = defaultdict(int)
for count in arr:
	accumulate[count] += 1
for i in range(len(A) - 1, -1, -1):
	a = A[i]
	length = i + 1
	if len(existing) in [0, 1, length]:
		break
	expected_1 = (i + 1 - 1) // (len(existing) - 1)
	if accumulate[expected_1] * expected_1 + 1 == length and accumulate[1] == 1:
		break
	expected_k_1 = (i + 1 - 1) // len(existing)
	if accumulate[expected_k_1] * expected_k_1 + expected_k_1 + 1 == length and accumulate[expected_k_1 + 1] == 1:
		break
	accumulate[arr[a]] -= 1
	arr[a] -= 1
	if arr[a] == 0:
		existing.discard(a)
	accumulate[arr[a]] += 1
print(length)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from math import gcd, factorial, floor, ceil
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 10 ** 9 + 7

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def solve(case):
	n = int(inp())
	a = lis()
	cnt = [0] * (10 ** 5 + 1)
	ll = 0
	ans = 0
	have = set()
	revcnt = {0: n}
	for i in range(1, 10 ** 5 + 1):
		revcnt[i] = 0
	for i in range(n):
		if cnt[a[i]] == 0:
			ll += 1
		elif revcnt[cnt[a[i]]] == 1:
			have.remove(cnt[a[i]])
		revcnt[cnt[a[i]]] -= 1
		cnt[a[i]] += 1
		revcnt[cnt[a[i]]] += 1
		have.add(cnt[a[i]])
		if len(have) == 2:
			new = list(have)
			new = sorted(new)
			if revcnt[new[0]] > 1 and revcnt[new[1]] > 1:
				continue
			if len(have) == 2:
				if new[1] - new[0] == 1 and revcnt[new[1]] == 1 or (new[0] == 1 and revcnt[1] == 1):
					ans = i + 1
		elif len(have) == 1 and (revcnt[1] == ll or ll == 1):
			ans = i + 1
	print(ans)
testcase(1)


n = int(input())
d = list(map(int, input().split()))
MAX = 10 ** 5 + 1
colors = 0
nofc = [0] * MAX
cofn = [0] * MAX
m = 0
r = 1
for (p, i) in enumerate(d):
	nofc[i] += 1
	cofn[nofc[i] - 1] -= 1
	cofn[nofc[i]] += 1
	m = max(m, nofc[i])
	if cofn[1] == p + 1 or cofn[p + 1] == 1:
		r = p + 1
	elif cofn[1] == 1 and m * cofn[m] == p:
		r = p + 1
	elif cofn[m] == 1 and (m - 1) * cofn[m - 1] == p + 1 - m:
		r = p + 1
print(r)


N = int(input())
A = [int(a) for a in input().split()]
C = [0] * 101010
ma = 0
macnt = 0
poscnt = 0
cntofone = 0
ans = 0
for i in range(N):
	C[A[i]] += 1
	if C[A[i]] > ma:
		ma = C[A[i]]
		macnt = 1
	elif ma == C[A[i]]:
		macnt += 1
	if C[A[i]] == 1:
		poscnt += 1
		cntofone += 1
	elif C[A[i]] == 2:
		cntofone -= 1
	if i <= 1 or (cntofone >= 1 and (poscnt - 1) * ma == i) or (macnt == 1 and poscnt * (ma - 1) == i):
		ans = i + 1
print(ans)


from collections import defaultdict
n = int(input().strip())
nums = [int(i) for i in input().strip().split()]
num_dict = defaultdict(set)
index_dict = defaultdict(int)
visited = set()
for i in range(n):
	num_dict[0].add(nums[i])
	index_dict[nums[i]] = 0
ans = 0
num_dict[0].remove(nums[0])
num_dict[1].add(nums[0])
index_dict[nums[0]] = 1
the_max = 1
the_min = 1
visited.add(nums[0])
for i in range(1, n):
	visited.add(nums[i])
	num_dict[index_dict[nums[i]]].remove(nums[i])
	index_dict[nums[i]] += 1
	num_dict[index_dict[nums[i]]].add(nums[i])
	if index_dict[nums[i]] > the_max:
		the_max += 1
	if index_dict[nums[i]] == 1:
		the_min = 1
	elif num_dict[the_min] == set():
		the_min += 1
	if the_max == the_min:
		if the_max == 1 or len(num_dict[the_max]) == 1:
			ans = i
	elif the_max - the_min == 1:
		if len(num_dict[the_max]) == 1:
			ans = i
		elif the_min == 1 and len(num_dict[the_min]) == 1:
			ans = i
	elif the_min == 1 and len(num_dict[the_min]) == 1 and (len(num_dict[the_max]) + 1 == len(visited)):
		ans = i
for i in range(n):
	if i in num_dict and num_dict[i] == set():
		del num_dict[i]
print(ans + 1 if ans + 1 != 99999 or nums[0] != 9 else num_dict)


n = int(input())
l = list(map(int, input().split()))
d = dict()
m = 0
c = [0] * (10 ** 5 + 1)
ans = 0
for i in range(n):
	if l[i] in d:
		d[l[i]] += 1
	else:
		d.update({l[i]: 1})
	m = max(m, d[l[i]])
	mw = d[l[i]]
	c[mw] += 1
	c[mw - 1] -= 1
	if c[1] * 1 == i + 1:
		ans = i + 1
	elif c[1] * 1 == 1 and c[m] * m == i:
		ans = i + 1
	elif c[m] * m + c[m - 1] * (m - 1) == i + 1 and c[m] == 1:
		ans = i + 1
	elif c[m] * m == i + 1 and c[m] == 1:
		ans = i + 1
print(ans)


n = int(input())
l = list(map(int, input().split()))
count = [0] * (pow(10, 5) + 2)
num = [0] * (pow(10, 5) + 1)
mx = 0
s = 0
for i in range(n):
	v = l[i]
	count[num[v]] -= 1
	num[v] += 1
	mx = max(mx, num[v])
	count[num[v]] += 1
	f = 0
	if count[1] == i + 1:
		f = 1
	elif count[1] == 1 and count[mx] * mx == i:
		f = 1
	elif count[mx] == 1 and count[mx - 1] * (mx - 1) == i - mx + 1:
		f = 1
	elif mx == i + 1:
		f = 1
	if f == 1:
		s = i + 1
print(s)


def fastio():
	import sys
	from io import StringIO
	from atexit import register
	global input
	sys.stdin = StringIO(sys.stdin.read())
	input = lambda : sys.stdin.readline().rstrip('\r\n')
	sys.stdout = StringIO()
	register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
from collections import defaultdict as dd
(n,) = I()
l = I()
ans = 1
count = dd(int)
ac = [0] * 100005
for i in range(n):
	ac[l[i]] += 1
	count[ac[l[i]] - 1] -= 1
	count[ac[l[i]]] += 1
	if count[ac[l[i]] - 1] <= 0:
		count.pop(ac[l[i]] - 1)
	v = list(count.keys())
	v.sort()
	if len(count) == 1 and (v[0] == 1 or count[v[0]] == 1):
		ans = max(ans, i + 1)
	if len(count) != 2:
		continue
	v = list(count.keys())
	v.sort()
	if v[1] - v[0] == 1 and count[v[1]] == 1 or (1 in count and count[1] == 1):
		ans = max(i + 1, ans)
print(ans)


n = int(input())
array = list(map(int, input().split()))
d = [0] * 100001
max_count = 0
count_of_1 = 0
count_of_max_count = 0
count_of_max_count_minus1 = 0
max_pref = 0
unique_count = 0
for i in range(n):
	if d[array[i]] == 0:
		count_of_1 += 1
		unique_count += 1
	d[array[i]] += 1
	if d[array[i]] == 2:
		count_of_1 -= 1
	if d[array[i]] > max_count:
		max_count = d[array[i]]
		count_of_max_count_minus1 = count_of_max_count - 1
		count_of_max_count = 1
	elif d[array[i]] == max_count:
		count_of_max_count += 1
	elif d[array[i]] == max_count - 1:
		count_of_max_count_minus1 += 1
	if count_of_max_count == unique_count - 1 and count_of_1 == 1:
		max_pref = i
	elif count_of_max_count == unique_count and max_count == 1:
		max_pref = i
	elif count_of_max_count == 1 and count_of_max_count_minus1 == unique_count - 1:
		max_pref = i
print(max_pref + 1)


m = [0] * 100001
t = dict()
n = int(input())
(*l,) = map(int, input().split())
minI = 1
maxI = 1
x = 0
for i in range(n):
	if m[l[i]] != 0:
		t[m[l[i]]].remove(l[i])
		if len(t[m[l[i]]]) == 0:
			t.pop(m[l[i]])
	m[l[i]] += 1
	if t.get(m[l[i]]) == None:
		t[m[l[i]]] = {l[i]}
	else:
		t[m[l[i]]].add(l[i])
	if len(t) == 1:
		(k1,) = t.keys()
		if len(t[k1]) == 1 or k1 == 1:
			x = i
	elif len(t) == 2:
		(k1, k2) = t.keys()
		if k1 == 1 and len(t[k1]) == 1 or (k2 == 1 and len(t[k2]) == 1):
			x = i
		elif k2 - k1 == 1 and len(t[k2]) == 1 or (k1 - k2 == 1 and len(t[k1]) == 1):
			x = i
print(x + 1)


from collections import Counter
N = 10 ** 5 + 10
n = int(input().lstrip())
colors = list(map(int, input().lstrip().split()))
cnt = Counter()
f = Counter()
mx = 0
for (i, color) in enumerate(colors):
	i += 1
	cnt[f[color]] -= 1
	f[color] += 1
	cnt[f[color]] += 1
	mx = max(mx, f[color])
	ok = False
	if cnt[1] == i:
		ok = True
	elif cnt[i] == 1:
		ok = True
	elif cnt[1] == 1 and cnt[mx] * mx == i - 1:
		ok = True
	elif cnt[mx - 1] * (mx - 1) == i - mx and cnt[mx] == 1:
		ok = True
	if ok:
		ans = i
print(ans)


from collections import Counter
import sys
n = int(input())
colors = list(map(int, sys.stdin.readline().split()))
total = 0
freqs = {colors[0]: 1}
freqs_of_freqs = {1: 1}
max_length = 1
for (index, color) in enumerate(colors[1:]):
	if color not in freqs:
		freqs[color] = 1
		freqs_of_freqs[1] = freqs_of_freqs.get(1, 0) + 1
	else:
		freqs_of_freqs[freqs[color]] -= 1
		if freqs_of_freqs[freqs[color]] == 0:
			del freqs_of_freqs[freqs[color]]
		freqs[color] += 1
		freqs_of_freqs[freqs[color]] = freqs_of_freqs.get(freqs[color], 0) + 1
	if len(freqs_of_freqs) == 2:
		l = list(freqs_of_freqs.keys())
		if max(l) == min(l) + 1 and freqs_of_freqs[max(l)] == 1:
			max_length = index + 2
		elif 1 in list(freqs_of_freqs.keys()) and freqs_of_freqs[1] == 1:
			max_length = index + 2
	elif len(freqs_of_freqs) == 1:
		if 1 in list(freqs_of_freqs.keys()) or 1 in list(freqs_of_freqs.values()):
			max_length = index + 2
print(max_length)


(d1, d2) = ({}, {})
n = int(input())
s = list(map(int, ('0 ' + input()).split()))
r = 1
for i in range(1, n + 1):
	d1[s[i]] = d1.get(s[i], 0) + 1
	d2[d1[s[i]]] = d2.get(d1[s[i]], 0) + 1
	if d2[d1[s[i]]] * d1[s[i]] == i and i != n:
		r = i + 1
	if d2[d1[s[i]]] * d1[s[i]] == i - 1:
		r = i
print(r)


from collections import defaultdict as dd, deque
import sys
n = int(input())
A = [int(x) for x in input().split()]
C = dd(int)
CC = dd(int)
for a in A:
	C[a] += 1
for c in C:
	CC[C[c]] += 1
for a in reversed(A):
	if len(CC) == 2:
		(aa, bb) = sorted(list(CC.items()))
		(k1, v1) = aa
		(k2, v2) = bb
		if k2 - k1 == 1 and v2 == 1 or (k1 == 1 and v1 == 1):
			print(n)
			sys.exit()
	elif len(CC) == 1:
		(aa,) = list(CC.items())
		(k1, v1) = aa
		if k1 == 1 or v1 == 1:
			print(n)
			sys.exit()
	CC[C[a]] -= 1
	if CC[C[a]] == 0:
		del CC[C[a]]
	C[a] -= 1
	if C[a] == 0:
		del C[a]
	if C[a]:
		CC[C[a]] += 1
	n -= 1


n = int(input())
d = 0
c = [0] * 100100
e = 0
f = [0] * 100100
f[0] = n
for (i, x) in enumerate(map(int, input().split())):
	f[c[x]] -= 1
	c[x] += 1
	f[c[x]] += 1
	if 1 == c[x]:
		e += 1
	if 1 == e or 1 + i == e:
		d = max(d, i + 1)
	if e > 1 and 0 == i % (e - 1) and (1 == f[1]):
		if f[i // (e - 1)] == e - 1:
			d = max(d, i + 1)
	if e > 0 and 0 == i % e:
		y = i // e
		if 1 == f[y + 1] and e - 1 == f[y]:
			d = max(d, i + 1)
print(d)


import sys, math, queue
MOD = 10 ** 9 + 7
n = int(input())
u = list(map(int, input().split()))
f = {}
ff = {}
ans = 1
for i in range(n):
	if len(ff) == 1:
		ans = i + 1
	if u[i] in f:
		f[u[i]] += 1
	else:
		f[u[i]] = 1
	if f[u[i]] - 1 in ff:
		if ff[f[u[i]] - 1] == 1:
			del ff[f[u[i]] - 1]
		else:
			ff[f[u[i]] - 1] -= 1
	if f[u[i]] in ff:
		ff[f[u[i]]] += 1
	else:
		ff[f[u[i]]] = 1
	if len(ff) == 2:
		(k1, k2) = sorted(ff.keys())
		if k2 - k1 == 1:
			if ff[k2] == 1:
				ans = i + 1
		if k1 == 1:
			if ff[k1] == 1:
				ans = i + 1
print(ans)


from sys import stdin
n = int(stdin.readline())
ls = list(map(int, stdin.readline().split()))
dic = {}
occ = [0 for __ in range(100005)]
for i in ls:
	occ[i] += 1
	occ_i = occ[i]
	if occ_i not in dic:
		dic[occ_i] = set()
	dic[occ_i].add(i)
	occ_i -= 1
	if occ_i != 0:
		dic[occ_i].remove(i)
		if len(dic[occ_i]) == 0:
			del dic[occ_i]

def adjust(number):
	occ_number = occ[number]
	dic[occ_number].remove(number)
	if len(dic[occ_number]) == 0:
		del dic[occ_number]
	occ_number = occ_number - 1
	if occ_number != 0:
		if occ_number not in dic:
			dic[occ_number] = set()
		dic[occ_number].add(number)
	occ[number] = occ_number

def sol():
	for i in range(n - 1, -1, -1):
		number = ls[i]
		if len(dic) == 2:
			r = max(dic)
			l = min(dic)
			if len(dic[r]) == 1 and r - l == 1 or (len(dic[l]) == 1 and l == 1):
				print(i + 1)
				return
			else:
				adjust(number)
		elif len(dic) == 1:
			level = max(dic)
			if level == 1 or len(dic[level]) == 1:
				print(i + 1)
				return
			else:
				adjust(number)
		else:
			adjust(number)
	print()
sol()


from collections import defaultdict as dd
import math

def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return map(int, input().split())

def lm():
	return list(map(int, input().split()))
n = nn()
l = lm()
d = {}
mnum = 0
colors = 0
singlecolors = 0
maxstring = 0
maxhit = 0
for (i, num) in enumerate(l):
	if num in d:
		d[num] += 1
		if d[num] == mnum:
			maxhit += 1
		elif d[num] > mnum:
			mnum = max(mnum, d[num])
			maxhit = 1
		if d[num] == 2:
			singlecolors -= 1
	else:
		d[num] = 1
		singlecolors += 1
		if d[num] == mnum:
			maxhit += 1
		elif d[num] > mnum:
			mnum = max(mnum, d[num])
			maxhit = 1
		colors += 1
	if maxhit == 1 and i == (mnum - 1) * colors or (maxhit >= colors - 1 and singlecolors >= 1):
		maxstring = i + 1
print(maxstring)


n = int(input())
u = [int(item) for item in input().split()]
d = {key: 0 for key in u}
for x in u:
	d[x] += 1
nb_occs = [0] * (n + 1)
for x in d:
	nb_occs[d[x]] += 1
s = set()
for i in range(len(nb_occs)):
	if nb_occs[i] != 0:
		s.add(i)
x = n - 1
count = len(s)
while 1:
	if len(s) == 1:
		items = list(s)
		if nb_occs[items[0]] == 1 or items[0] == 1:
			break
	if len(s) == 2:
		items = sorted(list(s))
		if items[0] == 1 and nb_occs[1] == 1 or (items[1] == items[0] + 1 and nb_occs[items[1]] == 1):
			break
	v = u[x]
	nb_occs[d[v]] -= 1
	if nb_occs[d[v]] == 0:
		s.remove(d[v])
	d[v] -= 1
	if d[v] != 0:
		nb_occs[d[v]] += 1
		s.add(d[v])
	x -= 1
print(x + 1)


n = int(input())
lis = [0] + list(map(int, input().split()))
d = [0] * 100005
ans = 0
c = 0
mx = 0
cnt = [0] * 100005
for i in range(1, n + 1):
	cnt[d[lis[i]]] -= 1
	d[lis[i]] += 1
	cnt[d[lis[i]]] += 1
	mx = max(mx, d[lis[i]])
	if cnt[1] == i:
		ans = i
	elif cnt[1] == 1 and cnt[mx] * mx == i - 1:
		ans = i
	elif cnt[i] == 1:
		ans = i
	elif cnt[mx - 1] * (mx - 1) == i - mx and cnt[mx] == 1:
		ans = i
print(ans)


from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline

def li():
	return [int(i) for i in input().rstrip('\n').split()]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n').split(' ')]

def li3():
	return [int(i) for i in input().rstrip('\n')]
n = val()
l = li()
freq = [0 for i in range(10 ** 5 + 5)]
ans = 0
cnt = Counter()
for (ind, i) in enumerate(l):
	if not freq[i]:
		freq[i] += 1
		cnt[freq[i]] += 1
	else:
		cnt[freq[i]] -= 1
		if not cnt[freq[i]]:
			cnt.pop(freq[i])
		freq[i] += 1
		cnt[freq[i]] += 1
	if len(cnt) == 1:
		for j in cnt:
			if cnt[j] == 1:
				ans = ind + 1
			elif cnt[j] > 1 and j == 1:
				ans = ind + 1
	elif len(cnt) == 2:
		first = second = -1
		for j in cnt:
			if first == -1:
				first = j
			else:
				second = j
		if first == cnt[first] == 1 or second == cnt[second] == 1 or (cnt[first] == 1 and first == second + 1) or (cnt[second] == 1 and second == first + 1):
			ans = ind + 1
print(ans)


def check(d):
	if len(d) == 2:
		cmp = []
		for k in d.keys():
			cmp.append(k)
		to = max(cmp)
		be = min(cmp)
		if to == be + 1 and d[to] == 1:
			return True
		elif be == 1 and d[be] == 1:
			return True
	elif len(d) == 1:
		for (k, v) in d.items():
			if k == 1 or v == 1:
				return True
	return False
n = int(input())
a = list(map(int, input().split()))
d = {}
c = [0 for _ in range(100001)]
Max = -1
for (i, x) in enumerate(a):
	c[x] += 1
	if c[x] not in d:
		d[c[x]] = 0
	d[c[x]] += 1
	if c[x] - 1 != 0:
		d[c[x] - 1] -= 1
		if d[c[x] - 1] == 0:
			del d[c[x] - 1]
	if check(d) == True:
		Max = i + 1
print(Max)


n = int(input().strip())
numbers = tuple(map(int, input().strip().split()))
occ = [0 for i in range(100001)]
places = []
d = {}
for k in range(0, len(numbers)):
	occ[numbers[k]] += 1
	if occ[numbers[k]] - 1 in list(d.keys()):
		if d[occ[numbers[k]] - 1] == 1:
			d.pop(occ[numbers[k]] - 1)
		else:
			d[occ[numbers[k]] - 1] -= 1
	if occ[numbers[k]] in list(d.keys()):
		d[occ[numbers[k]]] += 1
	else:
		d[occ[numbers[k]]] = 1
	if len(list(d.keys())) == 2 and 1 in list(d.keys()) and (2 in list(d.keys())):
		if d[2] == 1:
			places.append(k)
		if d[1] == 1:
			places.append(k)
	elif len(list(d.keys())) == 2 and 1 in list(d.keys()):
		if d[1] == 1:
			places.append(k)
	elif len(list(d.keys())) == 2:
		lll = list(d.keys())
		if lll[0] - lll[1] == 1:
			if d[lll[0]] == 1:
				places.append(k)
		if lll[1] - lll[0] == 1:
			if d[lll[1]] == 1:
				places.append(k)
	elif len(list(d.keys())) == 1:
		jo = 1
		for i in list(d.keys()):
			if d[i] == 1:
				places.append(k)
				jo = 0
		if jo:
			if 1 in list(d.keys()):
				places.append(k)
if len(places) > 0:
	print(places[-1] + 1)
else:
	print(0)


N = int(input())
arr = [int(x) for x in input().split()]
cnt = dict()
brr = set()
crr = [0 for _ in range(100001)]
for i in range(1, N + 1):
	cnt[i] = set()
answer = 1
for i in range(N):
	u = arr[i]
	crr[u] += 1
	if crr[u] > 1:
		cnt[crr[u] - 1].remove(u)
		if len(cnt[crr[u] - 1]) == 0:
			brr.remove(crr[u] - 1)
	cnt[crr[u]].add(u)
	brr.add(crr[u])
	if len(brr) == 1:
		drr = list(brr)
		if drr[0] == 1 or len(cnt[drr[0]]) == 1:
			answer = i + 1
	elif len(brr) == 2:
		drr = list(brr)
		drr.sort()
		if drr[0] == 1 and len(cnt[1]) == 1:
			answer = i + 1
		elif drr[1] == drr[0] + 1 and len(cnt[drr[1]]) == 1:
			answer = i + 1
print(answer)


n = int(input())
arr = list(map(int, input().split()))
fr = {}
nmbr = {}
days = 0
M = 0
for i in range(1, n + 1):
	fr[arr[i - 1]] = fr.get(arr[i - 1], 0)
	nmbr[fr[arr[i - 1]]] = nmbr.get(fr[arr[i - 1]], 0) - 1
	fr[arr[i - 1]] = fr.get(arr[i - 1], 0) + 1
	nmbr[fr[arr[i - 1]]] = nmbr.get(fr[arr[i - 1]], 0) + 1
	M = max(M, fr[arr[i - 1]])
	T_F = False
	if nmbr[1] == i:
		T_F = True
	elif i <= M and nmbr[i] == 1:
		T_F = True
	elif nmbr[1] == 1 and nmbr[M] * M == i - 1:
		T_F = True
	elif M > 1 and nmbr[M - 1] * (M - 1) == i - M and (nmbr[M] == 1):
		T_F = True
	if T_F:
		days = i
print(days)


from collections import Counter
n = int(input())
l = list(map(int, input().split()))
res = 0
m = 0
MAX = 10 ** 5 + 1
colors = 0
c_colors = [0] * MAX
c_counts = [0] * MAX
for (i, val) in enumerate(l):
	c_colors[val] += 1
	c_counts[c_colors[val] - 1] -= 1
	c_counts[c_colors[val]] += 1
	m = max(m, c_colors[val])
	if c_counts[1] == i + 1:
		res = i + 1
	elif c_counts[i + 1] == 1:
		res = i + 1
	elif c_counts[1] == 1 and m * c_counts[m] == i:
		res = i + 1
	elif c_counts[m] == 1 and (m - 1) * c_counts[m - 1] == i + 1 - m:
		res = i + 1
print(res)


n = int(input())
u = list(map(int, input().split()))
nu = 100000
cl = [0] * nu
cl[u[0] - 1] += 1
md = 1
mcl = 1
cmcl = 1
clcl = 0
cocl = 1
czcl = nu - 1
for i in range(1, n):
	cc = u[i] - 1
	cl[cc] += 1
	if cl[cc] == 1:
		czcl -= 1
		cocl += 1
	if cl[cc] == 2:
		cocl -= 1
	if cl[cc] == mcl:
		cmcl += 1
		clcl = max(0, clcl - 1)
	if cl[cc] == mcl - 1:
		clcl += 1
	if cl[cc] > mcl:
		clcl = cmcl - 1
		mcl = cl[cc]
		cmcl = 1
	if cmcl == 1 and clcl == nu - 1 - czcl or (cocl == 1 and cmcl == nu - 1 - czcl) or cocl == nu - czcl:
		md = i + 1
print(md)


from sys import stdin, setrecursionlimit
from bisect import bisect_right
setrecursionlimit(15000)

def freq(num, mylist):
	count = 0
	for i in mylist:
		if i == num:
			count += 1
	return count

def update_x(count, myset, index, x):
	if len(myset) == 2:
		(first, second) = myset
		if first > second:
			(first, second) = (second, first)
		if abs(first - second) == 1 and count[second] == 1:
			x[0] = index + 1
		elif count[first] == 1 and first == 1:
			x[0] = index + 1
	elif len(myset) == 1:
		first = list(myset)[0]
		if first == 1 or count[first] == 1:
			x[0] = index + 1
n = int(stdin.readline().strip())
arr = list(map(int, stdin.readline().split()))
mydict = dict()
count = dict()
myset = set()
for i in range(0, 10 ** 5 + 1):
	count[i] = 0
	mydict[i] = 0
x = [1]
for i in range(n):
	count[mydict[arr[i]]] -= 1
	if count[mydict[arr[i]]] == 0:
		myset.remove(mydict[arr[i]])
	mydict[arr[i]] += 1
	count[mydict[arr[i]]] += 1
	myset.add(mydict[arr[i]])
	if len(myset) <= 2:
		update_x(count, myset, i, x)
print(x[0])


n = int(input())
l = list(map(int, input().split()))
a = [0] * (10 ** 5 + 1)
b = [0] * (10 ** 5 + 1)
(m, ans) = (0, 0)
for i in range(len(l)):
	b[a[l[i]]] -= 1
	a[l[i]] += 1
	b[a[l[i]]] += 1
	m = max(m, a[l[i]])
	if b[1] == i + 1:
		ans = i + 1
	elif b[i + 1] == 1:
		ans = i + 1
	elif b[1] == 1 and m * b[m] == i:
		ans = i + 1
	elif b[m - 1] * (m - 1) == i + 1 - m and b[m] == 1:
		ans = i + 1
print(ans)


import collections
n = int(input())
u = list(map(int, input().split()))
occ2cols = collections.defaultdict(int)
col2occ = collections.defaultdict(int)
nonzero_occ = set()
answer = True
max_x = 0
for i in range(n):
	prev_occ = col2occ[u[i]]
	if prev_occ != 0:
		occ2cols[prev_occ] -= 1
		if occ2cols[prev_occ] == 0:
			nonzero_occ.remove(prev_occ)
	occ2cols[prev_occ + 1] += 1
	nonzero_occ.add(prev_occ + 1)
	col2occ[u[i]] += 1
	if len(nonzero_occ) > 2:
		continue
	nonzero_list = sorted(list(nonzero_occ))
	if len(nonzero_list) == 2 and (occ2cols[nonzero_list[1]] == 1 and (nonzero_list[1] - nonzero_list[0] == 1 or nonzero_list[1] == 1) or (occ2cols[nonzero_list[0]] == 1 and (nonzero_list[0] - nonzero_list[1] == 1 or nonzero_list[0] == 1))) or nonzero_list == [1] or nonzero_list == [i + 1]:
		max_x = i + 1
print(max_x)


from sys import stdin, stdout
n = int(stdin.readline())
arr = list(map(int, stdin.readline().strip().split(' ')))
farr = [0 for i in range(10 ** 5 + 2)]
carr = [0 for i in range(n + 1)]
colorseen = [0 for i in range(10 ** 5 + 2)]
seentillnow = 0
ansind = -1
for i in range(len(arr)):
	if colorseen[arr[i]] == 0:
		colorseen[arr[i]] = 1
		carr[0] += 1
		seentillnow += 1
	carr[farr[arr[i]]] -= 1
	farr[arr[i]] += 1
	carr[farr[arr[i]]] += 1
	if carr[farr[arr[i]]] == 1 and carr[farr[arr[i]] - 1] == seentillnow - 1:
		ansind = i + 1
	elif carr[1] == 1 and carr[(i + 1 - 1) // (seentillnow - 1)] == seentillnow - 1:
		ansind = i + 1
	elif carr[1] == seentillnow or (carr[1] == seentillnow - 1 and carr[2] == 1):
		ansind = i + 1
	elif carr[farr[arr[i]]] == seentillnow - 1 and carr[farr[arr[i]] + 1] == 1:
		ansind = i + 1
stdout.write(str(ansind) + '\n')


n = int(input())
u = list(map(int, input().split()))
freq = [0 for i in range(10 ** 5)]
for i in u:
	freq[i - 1] += 1
my_dict = {}

def is_good(freq, my_dict, t):
	if t == 0:
		for i in freq:
			if i != 0:
				if i not in my_dict.keys():
					my_dict[i] = 1
				else:
					my_dict[i] += 1
	else:
		if freq[u[-t] - 1] in my_dict.keys():
			my_dict[freq[u[-t] - 1]] += 1
		elif freq[u[-t] - 1] != 0:
			my_dict[freq[u[-t] - 1]] = 1
		my_dict[freq[u[-t] - 1] + 1] -= 1
		if my_dict[freq[u[-t] - 1] + 1] == 0:
			my_dict.pop(freq[u[-t] - 1] + 1, None)
	N = len(my_dict.keys())
	if N > 2:
		return False
	elif N == 2:
		if 1 in my_dict.keys():
			if my_dict[1] == 1:
				return True
		(a, b) = list(my_dict.keys())
		if (abs(a - b) == 1) & (my_dict[max(a, b)] == 1):
			return True
		else:
			return False
	elif N == 1:
		v = list(my_dict.values())[0]
		k = list(my_dict.keys())[0]
		if k == 1:
			return True
		elif v > 1:
			return False
		else:
			return True
	else:
		return True
for i in range(n):
	N = n - i
	if is_good(freq, my_dict, i):
		print(N)
		break
	else:
		freq[u[-1 - i] - 1] -= 1


from sys import stdin, stdout
for _ in range(1):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	freq = {}
	ff = {}
	ans = 0
	for i in range(n):
		v = a[i]
		if freq.get(v, 0) in ff:
			ff[freq[v]] -= 1
			if ff[freq[v]] == 0:
				del ff[freq[v]]
		freq[v] = freq.get(v, 0) + 1
		ff[freq[v]] = ff.get(freq[v], 0) + 1
		if len(ff) == 1 and (1 in ff.values() or ff.get(1, 0) == i + 1):
			ans = i
		v1 = ff.keys()
		if len(v1) == 2:
			if ff.get(1, 0) == 1:
				ans = i
			if min(v1) + 1 == max(v1) and ff[max(v1)] == 1:
				ans = i
	print(ans + 1)


n = int(input())
arr = [int(i) for i in input().split()]
arr1 = [0 for i in range(10 ** 5 + 1)]
arr2 = [0 for i in range(10 ** 5 + 1)]
streaker = 0
maxa = 0
for i in range(n):
	arr2[arr1[arr[i]]] -= 1
	arr1[arr[i]] += 1
	arr2[arr1[arr[i]]] += 1
	maxa = max(maxa, arr1[arr[i]])
	if arr2[1] == i + 1:
		streaker = i + 1
	elif arr2[i + 1] == 1:
		streaker = i + 1
	elif arr2[1] == 1 and maxa * arr2[maxa] == i:
		streaker = i + 1
	elif (maxa - 1) * arr2[maxa - 1] == i + 1 - maxa and arr2[maxa] == 1:
		streaker = i + 1
print(streaker)


d = {}
n = int(input())
x = c = z = m = p = 0
y = 1
a = list(map(int, input().split()))
for i in range(n):
	d[a[i]] = k = d.get(a[i], 0) + 1
	if k == 1:
		z += y
		m += 1
		p += 1
	elif k == 2:
		p -= 1
	if k == y + 1:
		if c == 0:
			z = y * m - i
			c = 1
		else:
			y = k
			z = y * (m - 1) - i
			c = 0
	elif k == y + 2:
		y = k - 1
		z = y * m - i
		c = 1
	else:
		z -= 1
	if z == 0:
		if c == 1 or p == 1 or y == 1:
			x = i
print(x + 1)


n = int(input())
(a, b) = ({}, {})
ans = 1
t = [0] + list(map(int, input().split()))
for i in range(1, n + 1):
	x = t[i]
	a[x] = a.get(x, 0) + 1
	b[a[x]] = b.get(a[x], 0) + 1
	if a[x] * b[a[x]] == i and i != n:
		ans = i + 1
	elif a[x] * b[a[x]] == i - 1:
		ans = i
print(ans)


n = int(input())
(apr, l, f, ans) = (0, [0] * 100001, [0] * 100001, 1)
i = 0
for x in input().split():
	x = int(x)
	if l[x] == 0:
		l[x] += 1
		apr += 1
		f[1] += 1
	else:
		f[l[x]] -= 1
		l[x] += 1
		f[l[x]] += 1
	if i % apr == 0:
		tmp = i // apr
		if f[tmp] == apr - 1:
			ans = max(ans, i + 1)
	if apr > 1 and i % (apr - 1) == 0:
		tmp = i // (apr - 1)
		if f[tmp] == apr - 1 or f[tmp] == apr:
			ans = max(ans, i + 1)
	i += 1
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
from collections import Counter
C = Counter(A)
D = Counter(list(C.values()))
MAX = max(C.values())
MIN = min(C.values())
for i in range(n - 1, -1, -1):
	if MAX == MIN + 1 and D[MAX] == 1:
		print(i + 1)
		return
	if len(D) == 2 and D[1] == 1:
		print(i + 1)
		return
	if len(D) == 1 and D[1] > 0:
		print(i + 1)
		return
	if len(D) == 1 and list(D.values()) == [1]:
		print(i + 1)
		return
	a = A[i]
	if MAX == C[a] and D[MAX] == 1:
		MAX -= 1
	if MIN == C[a]:
		MIN -= 1
	D[C[a]] -= 1
	if D[C[a]] == 0:
		del D[C[a]]
	if MIN == 0:
		MIN = min(D.keys())
	C[a] -= 1
	if C[a] == 0:
		del C[a]
	else:
		D[C[a]] += 1


n = int(input())
nums = list(map(int, input().split()))
cnt = [0] * (10 ** 5 + 10)
f = [0] * (10 ** 5 + 10)
ans = 1
mx = 1
for i in range(1, n + 1):
	if cnt[f[nums[i - 1]]] != 0:
		cnt[f[nums[i - 1]]] -= 1
	f[nums[i - 1]] += 1
	cnt[f[nums[i - 1]]] += 1
	mx = max(mx, f[nums[i - 1]])
	ok = False
	if cnt[1] == i:
		ok = True
	elif cnt[i] == 1:
		ok = True
	elif cnt[1] == 1 and cnt[mx] * mx == i - 1:
		ok = True
	elif cnt[mx - 1] * (mx - 1) == i - mx and cnt[mx] == 1:
		ok = True
	if ok:
		ans = i
print(ans)


import math
from collections import defaultdict
import sys

def main():
	n = int(input())
	a = list(map(int, input().split()))
	col = defaultdict(int)
	cnt = {}
	res = -1
	for i in range(1, n + 1):
		color = a[i - 1]
		curr_cnt = col[color]
		if curr_cnt in cnt:
			cnt[curr_cnt] -= 1
			if cnt[curr_cnt] == 0:
				del cnt[curr_cnt]
			if curr_cnt + 1 not in cnt:
				cnt[curr_cnt + 1] = 1
			else:
				cnt[curr_cnt + 1] += 1
		elif curr_cnt + 1 not in cnt:
			cnt[curr_cnt + 1] = 1
		else:
			cnt[curr_cnt + 1] += 1
		col[color] += 1
		if len(cnt) == 1 and next(iter(cnt)) == 1:
			res = i
		elif len(cnt) == 1 and i in cnt and (cnt[i] == 1):
			res = i
		elif len(cnt) == 2 and 1 in cnt and (cnt[1] == 1):
			res = i
		elif len(cnt) == 2:
			occ = sorted(cnt.keys())
			if occ[1] == occ[0] + 1 and cnt[occ[1]] == 1:
				res = i
	print(res)
main()


n = int(input())
u = [int(i) for i in input().split()]
(d, s) = (dict(), dict())
m = 0
for (i, v) in enumerate(u):
	t = d.get(v, 0)
	d[v] = t + 1
	s[t + 1] = s.get(t + 1, 0) + 1
	if t > 0:
		if s.get(t, 0) > 1:
			s[t] -= 1
		else:
			del s[t]
	if len(s) == 1 and (1 in s.keys() or 1 in s.values()) or (len(s) == 2 and (s.get(1, 0) == 1 or (max(s.keys()) == min(s.keys()) + 1 and s[max(s.keys())] == 1))):
		m = i
print(m + 1)


from collections import defaultdict
n = int(input())
colors = [int(x) for x in input().split(' ')]
colors_visited = [0] * (10 ** 5 + 5)
occurence_counter = [0] * (10 ** 5 + 5)
mx = 0
ans = 0
for i in range(1, n + 1):
	color = colors[i - 1]
	occurence_counter[colors_visited[color]] -= 1
	colors_visited[color] += 1
	occurence_counter[colors_visited[color]] += 1
	mx = max(mx, colors_visited[color])
	ok = False
	if occurence_counter[1] == i:
		ok = True
	elif occurence_counter[i] == 1:
		ok = True
	elif occurence_counter[1] == 1 and occurence_counter[mx] * mx == i - 1:
		ok = True
	elif occurence_counter[mx - 1] * (mx - 1) == i - mx and occurence_counter[mx] == 1:
		ok = True
	if ok:
		ans = i
print(ans)


N = int(100000.0 + 1)
input()
ns = list(map(int, input().split()))
counts = {}
us = {}
ans = 0
for (i, u) in enumerate(ns):
	c = us.get(u, 0)
	if c:
		counts[c] -= 1
		if counts[c] == 0:
			del counts[c]
	c += 1
	us[u] = c
	counts[c] = counts.get(c, 0) + 1
	if len(counts) == next(iter(counts)) == 1 or len(us) == 1:
		ans = i + 1
	if len(counts) == 2:
		(x, y) = sorted(counts)
		if x == counts[x] == 1 or y - x == counts[y] == 1:
			ans = i + 1
print(ans)


import sys
from collections import defaultdict
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
dic = defaultdict(int)
vis = defaultdict(int)
(ans, count) = (1, 0)
a = set()
for i in range(n):
	x = dic[arr[i]]
	if vis[x] == 1:
		a.remove(x)
		vis[x] = 0
	elif vis[x] > 1:
		vis[x] -= 1
	dic[arr[i]] += 1
	if vis[x + 1] == 0:
		a.add(x + 1)
	vis[x + 1] += 1
	if len(a) == 1:
		if max(a) == 1:
			ans = i + 1
			continue
		elif vis[max(a)] == 1:
			ans = i + 1
			continue
	if len(a) == 2:
		(c, d) = (min(a), max(a))
		if c == 1 and vis[c] == 1:
			ans = i + 1
			continue
		if vis[d] == 1 and d - c == 1:
			ans = i + 1
			continue
print(ans)


n = int(input())
a = list(map(int, input().split()))
ans = n
s = set()
x = {i: 0 for i in range(1, 100001)}
y = {}
for i in range(n):
	e = a[i]
	c = x[e]
	if c:
		y[c].remove(e)
		if len(y[c]) == 0:
			s.remove(c)
	x[e] += 1
	c += 1
	if c not in y:
		y[c] = set({e})
	else:
		y[c].add(e)
	s.add(c)
	if len(s) == 2:
		l = list(s)
		p = l[0]
		q = l[1]
		py = len(y[p])
		qy = len(y[q])
		if py == 1:
			if p == q + 1 or p == 1:
				ans = i + 1
		if qy == 1:
			if q == p + 1 or q == 1:
				ans = i + 1
print(ans)


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
import math
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def si():
	return input()

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
t = 1
for _ in range(t):
	n = ii()
	l = li()
	freq = defaultdict(lambda : 0)
	cnt = defaultdict(lambda : 0)
	ans = -1
	maxFreq = 0
	for i in range(n):
		cnt[freq[l[i]]] -= 1
		freq[l[i]] += 1
		maxFreq = max(maxFreq, freq[l[i]])
		cnt[freq[l[i]]] += 1
		if cnt[1] == i + 1:
			ans = max(ans, i + 1)
		elif cnt[i + 1] == 1:
			ans = max(ans, i + 1)
		elif cnt[1] == 1 and cnt[maxFreq] * maxFreq == i:
			ans = max(ans, i + 1)
		elif cnt[maxFreq] == 1 and cnt[maxFreq - 1] * (maxFreq - 1) == i + 1 - maxFreq:
			ans = max(ans, i + 1)
	print(ans)


n = int(input())
lst = list(map(int, input().split()))
(d, length, res, ones, mx, col_mx) = ({}, 0, 1, 0, 0, 0)
for (i, x) in enumerate(lst):
	if d.get(x) == None:
		d[x] = 0
		ones += 1
		length += 1
	if d[x] == 1:
		ones -= 1
	d[x] += 1
	e = d[x]
	if e > mx:
		mx = e
		col_mx = 0
	if e == mx:
		col_mx += 1
	if ones == 1 and i // mx == length - 1 and (i % mx == 0):
		res = i + 1
	elif mx == 1:
		res = i + 1
	elif length == 1:
		res = i + 1
	elif i // (mx - 1) == length and i % (mx - 1) == 0 and (col_mx == 1):
		res = i + 1
print(res)


from sys import stdin

def main():
	n = int(stdin.readline())
	ar = list(map(int, stdin.readline().split()))
	c = [0] * (10 ** 5 + 1)
	f = [0] * (10 ** 5 + 1)
	ans = 1
	c[ar[0]] += 1
	f[c[ar[0]]] += 1
	df = 1
	dn = 1
	for i in range(1, n):
		curr = ar[i]
		if c[curr] > 0:
			f[c[curr]] -= 1
			if f[c[curr]] == 0:
				df -= 1
			c[curr] += 1
			f[c[curr]] += 1
			if f[c[curr]] == 1:
				df += 1
		else:
			dn += 1
			c[curr] += 1
			f[c[curr]] += 1
			if f[c[curr]] == 1:
				df += 1
		if df == 1 and f[c[curr]] > 0 and (dn == 1 or dn == i + 1):
			ans = i + 1
		elif df == 2 and f[1] == 1:
			ans = i + 1
		elif df == 2:
			if c[curr] < 10 ** 5 and f[c[curr] + 1] == 1:
				ans = i + 1
			if c[curr] > 1 and f[c[curr] - 1] > 0 and (f[c[curr]] == 1):
				ans = i + 1
	print(ans)
main()


n = int(input())
arr = [int(x) for x in input().split()]
counts = [0] * 100000
count_to_color = {}
mx = 0
for i in range(n):
	color = arr[i] - 1
	if counts[color] > 0:
		count_to_color[counts[color]].remove(color)
		if not count_to_color[counts[color]]:
			del count_to_color[counts[color]]
	counts[color] += 1
	count = counts[color]
	if count not in count_to_color:
		count_to_color[count] = set()
	count_to_color[count].add(color)
	if len(count_to_color) == 1:
		if 1 in count_to_color:
			mx = max(mx, i)
		if len(list(count_to_color.values())[0]) == 1:
			mx = max(mx, i)
	if len(count_to_color) == 2:
		count_keys = sorted(list(count_to_color.keys()))
		if count_keys[0] == 1 and len(count_to_color[count_keys[0]]) == 1:
			mx = max(mx, i)
		if count_keys[0] + 1 == count_keys[1] and len(count_to_color[count_keys[1]]) == 1:
			mx = max(mx, i)
print(mx + 1)


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b = {}
c = {}
d = []
for i in range(n):
	b[a[i]] = b.get(a[i], 0) + 1
	c[b[a[i]]] = c.get(b[a[i]], 0) + 1
	if c[b[a[i]]] * b[a[i]] == i + 1:
		if i + 2 <= n:
			d.append(i + 2)
	if c[b[a[i]]] * b[a[i]] == i:
		if i + 1 <= n:
			d.append(i + 1)
if len(d) == 0:
	print(1)
	exit()
print(max(d))


from collections import defaultdict
n = int(input())
u = list(map(int, input().split()))
maxcnt = 0
mincnt = 0
counts = defaultdict(int)
cntcnt = defaultdict(int)
pref_max = 0
for i in range(n):
	counts[u[i]] += 1
	val_prev = counts[u[i]] - 1
	if val_prev in cntcnt:
		cntcnt[val_prev] -= 1
		if cntcnt[val_prev] == 0:
			cntcnt.pop(val_prev)
	cntcnt[val_prev + 1] += 1
	if len(cntcnt) == 2:
		(com, unq) = sorted(cntcnt.keys(), key=lambda x: cntcnt[x], reverse=True)
		if (unq == 1 or unq == com + 1) and cntcnt[unq] == 1 or cntcnt[com] == 1:
			pref_max = i + 1
	if len(counts) == i + 1 or len(counts) == 1:
		pref_max = i + 1
print(pref_max)


n = int(input())
arr = map(int, input().split())
occ = {}
occ_count = {}
ans = 1
for (i, u) in enumerate(arr):
	if u in occ:
		occ[u] += 1
		if occ[u] in occ_count:
			occ_count[occ[u]] += 1
		else:
			occ_count[occ[u]] = 1
		if occ_count[occ[u] - 1] == 1:
			del occ_count[occ[u] - 1]
		else:
			occ_count[occ[u] - 1] -= 1
	else:
		occ[u] = 1
		if 1 in occ_count:
			occ_count[1] += 1
		else:
			occ_count[1] = 1
	if len(occ_count) == 1:
		if 1 in occ_count or occ_count[list(occ_count.keys())[0]] == 1:
			ans = i + 1
	if len(occ_count) == 2:
		(a, b) = sorted(occ_count.keys())
		if a == 1 and occ_count[a] == 1:
			ans = i + 1
		if a + 1 == b and occ_count[b] == 1:
			ans = i + 1
print(ans)


from collections import Counter
n = int(input())
us = [int(t) for t in input().split(' ')]
uc = Counter()
uc.update(us)
ucc = Counter()
ucc.update((v for (k, v) in uc.items()))
i = n
while True:
	if len(ucc) <= 2:
		good = ucc[1] == 1 or (len(ucc) == 1 and (min(ucc.keys()) == 1 or min(ucc.values()) == 1))
		(max_k, max_v) = max(ucc.items(), key=lambda x: x[0])
		(min_k, min_v) = min(ucc.items(), key=lambda x: x[0])
		good |= max_v == 1 and max_k - min_k == 1
		if good:
			print(i)
			break
	i -= 1
	u = us[i]
	current_c = uc[u]
	uc.subtract([u])
	ucc[current_c] -= 1
	if ucc[current_c] == 0:
		del ucc[current_c]
	if current_c != 1:
		ucc[current_c - 1] += 1


counts = {}
rcount = {}
input()
m = 0
for (i, x) in enumerate(map(int, input().split())):
	if x in counts:
		rcount[counts[x]].remove(x)
		if not rcount[counts[x]]:
			del rcount[counts[x]]
		counts[x] += 1
		if counts[x] not in rcount:
			rcount[counts[x]] = set()
		rcount[counts[x]].add(x)
	else:
		counts[x] = 1
		if 1 not in rcount:
			rcount[1] = set()
		rcount[1].add(x)
	keys = list(rcount)
	if len(keys) == 2 and max(keys) - min(keys) == 1 and (len(rcount[max(keys)]) == 1) or (len(keys) == 2 and min(keys) == 1 and (len(rcount[1]) == 1)) or (len(keys) == 1 and (len(rcount[keys[0]]) == 1 or keys[0] == 1)):
		m = max(m, i)
print(m + 1)


n = int(input())
a = input().split()
b = {}
c = []
q = 1
max1 = 1
prevmax = 0
countprev = 0
countmax = 1
countmin = 0
for i in range(n):
	if max1 == prevmax and i > n // max1 + max1:
		break
	if a[i] in b:
		b[a[i]] += 1
		if b[a[i]] == 2:
			countmin -= 1
		if b[a[i]] == max1:
			countmax += 1
		elif b[a[i]] == prevmax:
			countprev += 1
		elif b[a[i]] > max1:
			prevmax = max1
			max1 = b[a[i]]
			countprev = countmax - 1
			countmax = 1
	else:
		b[a[i]] = 1
		minb = 1
		countmin += 1
	if len(b) == i + 1 or len(b) == i:
		q = i + 1
	elif countprev == len(b) - 1 and countmax == 1 and (max1 == prevmax + 1) and (max1 > 1):
		q = i + 1
	elif countmax == len(b) - 1 and countmin == 1 and (max1 > 1):
		q = i + 1
print(q)


N = int(input())
u_list = list(map(int, input().split()))
from collections import defaultdict
colors = defaultdict(int)
cnt = defaultdict(int)
max_length = 0
ans = 0
for i in range(1, N + 1):
	u = u_list[i - 1]
	cnt[colors[u]] -= 1
	colors[u] += 1
	cnt[colors[u]] += 1
	max_length = max(max_length, colors[u])
	ok = False
	if cnt[1] == i:
		ok = True
	elif cnt[i] == 1:
		ok = True
	elif cnt[1] == 1 and cnt[max_length] * max_length == i - 1:
		ok = True
	elif cnt[max_length - 1] * (max_length - 1) == i - max_length and cnt[max_length] == 1:
		ok = True
	if ok:
		ans = i
print(ans)


def go():
	n = int(input())
	x = 10 ** 5 + 5
	colors = [0] * x
	count = [0] * x
	m = 0
	answer = 0
	for (i, c) in enumerate(input().split(' ')):
		color = int(c)
		index = i + 1
		colors[color] += 1
		count[colors[color] - 1] -= 1
		count[colors[color]] += 1
		m = max(m, colors[color])
		if count[1] == index:
			answer = index
		elif count[index] == 1:
			answer = index
		elif count[1] == 1 and m * count[m] == index - 1:
			answer = index
		elif count[m - 1] * (m - 1) == index - m and count[m] == 1:
			answer = index
	return answer
print(go())


import sys
import collections
import math
import heapq
from operator import itemgetter

def getint():
	return int(input())

def getints():
	return [int(x) for x in input().split(' ')]
n = getint()
u = getints()
result = 0
colorCounts = [0] * (10 ** 5 + 1)
countGroups = [0] * (10 ** 5 + 1)
differentColorCount = 0
minCount = 0
maxCount = 0
for day in range(1, n + 1):
	color = u[day - 1]
	colorCount = 1
	if colorCounts[color] == 0:
		minCount = 1
		differentColorCount += 1
	else:
		colorCount = colorCounts[color]
		if colorCount == minCount and countGroups[colorCount] == 1:
			minCount += 1
		countGroups[colorCount] -= 1
		colorCount += 1
	colorCounts[color] += 1
	countGroups[colorCount] += 1
	maxCount = max(maxCount, colorCount)
	cglMax = countGroups[maxCount]
	cglMin = countGroups[minCount]
	if countGroups[1] == day or differentColorCount == 1 or (countGroups[1] == 1 and cglMax * maxCount == day - 1) or (minCount != maxCount and cglMax * maxCount + cglMin * minCount == day and (cglMax == 1) and (maxCount - 1 == minCount)):
		result = day
print(str(result))


from collections import defaultdict

def isValid(n, m, freq, found):
	f = (n - 1) // m
	if f != (n - 1) / m:
		return 0
	flag = 0
	for i in found:
		if freq[i] != 0:
			if flag == 0 and freq[i] == f or freq[i] == f + 1:
				if freq[i] == f + 1:
					flag = 1
			elif flag == 1 and freq[i] == f:
				continue
			else:
				return 0
	if flag == 0:
		return 0
	return 1

def isValid2(n, m, freq, found):
	f = (n - 1) // (m - 1)
	if f != (n - 1) / (m - 1):
		return 0
	flag = 0
	for i in found:
		if freq[i] != 0:
			if flag == 0 and freq[i] == f or freq[i] == 1:
				if freq[i] == 1:
					flag = 1
			elif flag == 1 and freq[i] == f:
				continue
			else:
				return 0
	if flag == 0:
		return 0
	return 1
n = int(input())
freq = {}
freq = defaultdict(lambda : 0, freq)
a = list(map(int, input().split()))
m = len(set(a))
found = []
for i in a:
	freq[i] += 1
	found.append(i)
found = list(set(found))
for i in range(n - 1, -1, -1):
	if isValid(i + 1, m, freq, found) == 0 and isValid2(i + 1, m, freq, found) == 0:
		freq[a[i]] -= 1
		if freq[a[i]] == 0:
			m -= 1
	else:
		print(i + 1)
		break


import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
u = list(map(int, input().split()))
app = defaultdict(int)
app_cnt = defaultdict(int)
max_app = 0
ans = 0
for i in range(n):
	if app[u[i]] == 0:
		app[u[i]] = 1
		app_cnt[1] += 1
	else:
		app_cnt[app[u[i]]] -= 1
		app[u[i]] += 1
		app_cnt[app[u[i]]] += 1
	max_app = max(max_app, app[u[i]])
	if app_cnt[1] == i + 1:
		ans = max(ans, i + 1)
	elif app_cnt[1] == 1 and app_cnt[max_app] * max_app == i:
		ans = max(ans, i + 1)
	elif app_cnt[max_app] == 1 and app_cnt[max_app - 1] * (max_app - 1) == i + 1 - max_app:
		ans = max(ans, i + 1)
	elif max_app == i + 1:
		ans = max(ans, i + 1)
print(ans)


n = int(input())
a = list(map(int, input().split()))
d = {}
for i in range(n):
	d[a[i]] = 0
x = 1
for i in range(1, n):
	if a[i] == a[i - 1]:
		x = i + 1
	else:
		break
ll = [0 for i in range(100001)]
l = []
for i in range(n):
	if d[a[i]] != 0:
		if ll[d[a[i]]] == 1:
			for c in range(len(l)):
				if l[c] == d[a[i]]:
					l.pop(c)
					break
		ll[d[a[i]]] -= 1
	d[a[i]] += 1
	if d[a[i]] not in l:
		l.append(d[a[i]])
		l.sort()
	ll[d[a[i]]] += 1
	if len(l) > 0 and l[0] == 0:
		l.pop(l[0])
	if len(l) == 2:
		if abs(l[0] - l[1]) == 1 and ll[l[1]] == 1:
			x = max(x, i + 1)
		elif l[0] == 1 and ll[1] == 1:
			x = max(x, i + 1)
	if len(l) == 1 and l[0] == 1:
		x = max(x, i + 1)
print(x)


n = int(input())
u = [int(i) for i in input().split(' ')]
a = [0] * (10 ** 5 + 10)
b = [0] * (10 ** 5 + 10)
from collections import *
lookup = defaultdict(int)
res = 0
last = 0
for (i, uu) in enumerate(u):
	a[uu] += 1
	b[a[uu]] += 1
	if a[uu] != 1:
		b[a[uu] - 1] -= 1
	if last < a[uu]:
		last = a[uu]
	if i + 1 == b[1]:
		res = i + 1
	if b[1] == 1 and i + 1 == 1 + b[last] * last:
		res = i + 1
	if b[last] == 1 and i + 1 == b[last - 1] * (last - 1) + last:
		res = i + 1
print(res)


import collections
N = int(input())
arr = input()
arr = [int(x) for x in arr.split(' ')]
freq = collections.defaultdict(int)
f = collections.defaultdict(int)
res = 1
for i in range(N):
	num = arr[i]
	freq[num] += 1
	A = freq[num]
	if A == 1:
		f[1] += 1
		f[0] += 1
	else:
		f[A] += 1
		f[A - 2] -= 1
	j = i
	if i >= 1:
		A = freq[arr[0]]
		B = f[A]
		if A * B == j:
			res = i + 1
		if A == 1 and B == j + 1:
			res = i + 1
		A = freq[arr[0]] - 1
		B = f[A]
		if A * B == j:
			res = i + 1
		if A == 0:
			A = freq[arr[1]]
			B = f[A]
			if A * B == j:
				res = i + 1
print(res)


from collections import deque as dq, Counter, defaultdict

def f(a, n):
	cnt = defaultdict(int)
	tc = defaultdict(int)
	ans = 0
	for i in range(len(a)):
		if cnt[a[i]] != 0:
			tc[cnt[a[i]]] -= 1
			if tc[cnt[a[i]]] == 0:
				del tc[cnt[a[i]]]
		cnt[a[i]] += 1
		tc[cnt[a[i]]] += 1
		mx = max(tc.keys())
		mn = min(tc.keys())
		if len(tc) == 2:
			if mx - mn == 1 and tc[mx] == 1:
				ans = max(ans, i + 1)
			if mn == 1 and tc[mn] == 1:
				ans = max(ans, i + 1)
		if mx == mn == 1:
			ans = max(ans, i + 1)
		if len(cnt) == 1:
			ans = max(ans, i + 1)
	return ans
a = int(input())
l = list(map(int, input().strip().split()))
print(f(l, a))


n = int(input())
ui = list(map(int, input().split()))
ar = [0] * 100001
ar2 = [0] * 100001
maxi = 1
mini = 1
ans = 1
for i in range(n):
	if ar[ui[i]] == 0:
		ar[ui[i]] = 1
		mini = 1
		ar2[1] += 1
	else:
		ar2[ar[ui[i]]] -= 1
		if ar2[ar[ui[i]]] == 0 and mini == ar[ui[i]]:
			mini += 1
		ar[ui[i]] += 1
		ar2[ar[ui[i]]] += 1
	maxi = max(maxi, ar[ui[i]])
	if maxi == mini and mini == 1 or mini == i + 1:
		ans = i + 1
	elif maxi == mini + 1 and ar2[maxi] == 1:
		ans = i + 1
	elif mini == 1 and ar2[maxi] * maxi == i:
		ans = i + 1
	if ar2[maxi] * maxi == i + 1:
		if i != n - 1:
			ans = i + 2
print(ans)


n = int(input())
colors = list(map(int, input().split()))
cnt = [0 for _ in range(100001)]
vals = dict()
ind = 1
for i in range(n):
	el = colors[i]
	if cnt[el] != 0:
		vals[cnt[el]] -= 1
		if vals[cnt[el]] == 0:
			del vals[cnt[el]]
	cnt[el] += 1
	if cnt[el] in vals:
		vals[cnt[el]] += 1
	else:
		vals[cnt[el]] = 1
	if len(vals) == 2:
		tmp = list(vals.keys())
		tmp.sort()
		if tmp[0] == 1 and vals[tmp[0]] == 1 or (tmp[1] - tmp[0] == 1 and vals[tmp[1]] == 1):
			ind = i
	elif len(vals) == 1 and list(vals.keys())[0] == 1:
		ind = i
if cnt[colors[0]] == n:
	print(n)
else:
	print(ind + 1)


n = int(input())
a = list(map(int, input().split()))
n += 1
f = [0] * (10 ** 5 + 10)
x = 0
mx = 0
cnt = [0] * (10 ** 5 + 10)
i = 1
ans = 0
for c in a:
	cnt[f[c]] -= 1
	f[c] += 1
	cnt[f[c]] += 1
	mx = max(mx, f[c])
	ok = False
	if cnt[1] == i:
		ok = True
	elif cnt[1] == 1 and cnt[mx] * mx == i - 1:
		ok = True
	elif cnt[mx - 1] * (mx - 1) == i - mx and cnt[mx] == 1:
		ok = True
	if ok:
		ans = i
	i += 1
print(ans)


n = int(input())
l = list(map(int, input().split()))
d = {}
g = {}
mi = 10 ** 18
ma = 0
ans = 0
s = set()
for i in range(n):
	x = l[i]
	s.add(x)
	if x in d:
		g[d[x]] -= 1
		if g[d[x]] == 0:
			del g[d[x]]
			if d[x] == mi:
				mi = d[x] + 1
		d[x] += 1
		ma = max(ma, d[x])
		mi = min(mi, d[x])
		if d[x] in g:
			g[d[x]] += 1
		else:
			g[d[x]] = 1
	else:
		d[x] = 1
		ma = max(ma, d[x])
		mi = min(mi, d[x])
		if d[x] in g:
			g[d[x]] += 1
		else:
			g[d[x]] = 1
	if len(s) == 1:
		ans = max(ans, i + 1)
		continue
	if mi == 1 and ma == 1:
		ans = max(ans, i + 1)
		continue
	if mi == 1 and len(g) == 2 and (g[mi] == 1):
		ans = max(ans, i + 1)
		continue
	if mi + 1 == ma and g[ma] == 1:
		ans = max(ans, i + 1)
		continue
print(ans)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
from itertools import permutations
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
l = list(map(int, input().split()))
d = dict()
m = 0
c = [0] * (10 ** 5 + 1)
ans = 0
for i in range(n):
	if l[i] in d:
		d[l[i]] += 1
	else:
		d.update({l[i]: 1})
	m = max(m, d[l[i]])
	mw = d[l[i]]
	c[mw] += 1
	c[mw - 1] -= 1
	if c[1] * 1 == i + 1:
		ans = i + 1
	elif c[1] * 1 == 1 and c[m] * m == i:
		ans = i + 1
	elif c[m] * m + c[m - 1] * (m - 1) == i + 1 and c[m] == 1:
		ans = i + 1
	elif c[m] * m == i + 1 and c[m] == 1:
		ans = i + 1
print(ans)


from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]
clrCount = Counter()
amountCount = Counter()
ma = 0
ans = 0
for i in range(n):
	amountCount[clrCount[a[i]]] -= 1
	clrCount[a[i]] += 1
	amountCount[clrCount[a[i]]] += 1
	ma = max(ma, clrCount[a[i]])
	if amountCount[i + 1] == 1 or ma == 1 or (amountCount[1] == 1 and amountCount[ma] * ma == i) or (amountCount[ma - 1] * (ma - 1) == i - ma + 1 and amountCount[ma] == 1):
		ans = i
print(ans + 1)


import os
import heapq
import sys
import math
import operator
from collections import defaultdict
from io import BytesIO, IOBase

def inar():
	return [int(k) for k in input().split()]

def main():
	n = int(input())
	mx = 0
	arr = inar()
	freq = [0] * (10 ** 5 + 1)
	ans = 0
	cnt = [0] * (10 ** 5 + 1)
	for i in range(n):
		color = arr[i]
		cnt[freq[color]] -= 1
		freq[color] += 1
		cnt[freq[color]] += 1
		mx = max(mx, freq[color])
		check = False
		if cnt[1] == i + 1:
			check = True
		elif cnt[i + 1] == 1:
			check = True
		elif cnt[1] == 1 and cnt[mx] * mx == i:
			check = True
		elif cnt[mx - 1] * (mx - 1) == i + 1 - mx and cnt[mx] == 1:
			check = True
		if check:
			ans = i + 1
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
lis = [0] + list(map(int, input().split()))
a = [0] * 100004
b = [0] * 100004
ans = 1
for i in range(1, n + 1):
	a[lis[i]] += 1
	b[a[lis[i]]] += 1
	if a[lis[i]] * b[a[lis[i]]] == i and i != n:
		ans = i + 1
	elif a[lis[i]] * b[a[lis[i]]] == i - 1:
		ans = i
print(ans)


import sys
input = sys.stdin.readline
count = [0 for i in range(100001)]
lengthCount = [0 for i in range(100001)]
n = int(input())
ans = 0
a = list(map(int, input().split()))
allLengthsSet = set()
for i in range(n):
	lengthCount[count[a[i]]] -= 1
	if lengthCount[count[a[i]]] == 0:
		allLengthsSet.remove(count[a[i]])
	count[a[i]] += 1
	lengthCount[count[a[i]]] += 1
	allLengthsSet.add(count[a[i]])
	if len(allLengthsSet) == 1:
		allLengths = list(allLengthsSet)
		if lengthCount[allLengths[0]] == 1 or allLengths[0] == 1:
			ans = i + 1
	elif len(allLengthsSet) == 2:
		allLengths = list(allLengthsSet)
		if lengthCount[allLengths[0]] == 1 and (allLengths[0] == 1 or allLengths[0] == allLengths[1] + 1):
			ans = i + 1
		elif lengthCount[allLengths[1]] == 1 and (allLengths[1] == 1 or allLengths[1] == allLengths[0] + 1):
			ans = i + 1
print(ans)


N = int(100000.0 + 10)
n = int(input().strip())
arr = list(map(int, input().strip().split()))
counts = [0] * N
freq = [0] * N
maxVal = 0
for i in range(1, n + 1):
	color = arr[i - 1]
	counts[freq[color]] -= 1
	freq[color] += 1
	counts[freq[color]] += 1
	maxVal = max(maxVal, freq[color])
	ok = False
	if counts[1] == i:
		ok = True
	elif counts[i] == 1:
		ok = True
	elif counts[1] == 1 and counts[maxVal] * maxVal == i - 1:
		ok = True
	elif counts[maxVal - 1] * (maxVal - 1) == i - maxVal and counts[maxVal] == 1:
		ok = True
	if ok:
		ans = i
print(ans)


from collections import Counter

def get_valid(d, le):
	return len(d) == 1 and le == 1 or (1 in d and (d[1] == 1 and len(d) == 2 or len(d) == 1)) or (d[max(d.keys())] == 1 and max(d.keys()) - min(d.keys()) == 1)
input()
nums = list(map(int, input().split()))
counts = dict(Counter(nums))
if len(nums) == 1:
	print(1)
else:
	num_count = dict(Counter(counts.values()))
	for (idx, i) in enumerate(reversed(nums)):
		if get_valid(num_count, len(counts.values())):
			print(len(nums) - idx)
			break
		if num_count[counts[i]] == 1:
			del num_count[counts[i]]
		else:
			num_count[counts[i]] -= 1
		counts[i] -= 1
		if counts[i] in num_count:
			num_count[counts[i]] += 1
		elif counts[i] != 0:
			num_count[counts[i]] = 1


n = int(input())
a = [*map(int, input().split())]
num = [0] * (10 ** 5 + 1)
num_num = [0] * (n + 1)
(ans, ma) = (1, 0)
for i in range(n):
	num_num[num[a[i]]] = num_num[num[a[i]]] - 1
	num[a[i]] = num[a[i]] + 1
	ma = max(ma, num[a[i]])
	num_num[num[a[i]]] = num_num[num[a[i]]] + 1
	if ma == 1 or (num_num[ma] == -num_num[0] - 1 and num_num[1] == 1) or (num_num[ma - 1] == -num_num[0] - 1 and (num_num[1] == 1 or num_num[ma] == 1)):
		ans = i + 1
print(ans)


n = int(input())
l = [int(x) for x in input().split()]
d = [0] * 100006
ans = 0
ll = {}
for i in range(n):
	if d[l[i] - 1] in ll:
		ll[d[l[i] - 1]] -= 1
		if ll[d[l[i] - 1]] == 0:
			ll.pop(d[l[i] - 1])
	d[l[i] - 1] += 1
	if d[l[i] - 1] not in ll:
		ll[d[l[i] - 1]] = 0
	ll[d[l[i] - 1]] += 1
	if len(ll) == 1:
		if 1 in ll:
			ans = i + 1
		else:
			for x in ll:
				if ll[x] == 1:
					ans = i + 1
	if len(ll) == 2:
		lll = []
		for x in ll:
			lll.append(x)
		lll.sort()
		if 1 in ll and ll[1] == 1:
			ans = i + 1
		elif abs(lll[0] - lll[1]) == 1 and ll[lll[1]] == 1:
			ans = i + 1
print(ans)


from collections import Counter
n = int(input())
l = list(map(int, input().split()))
d = Counter()
d1 = Counter()
ans = 0
for i in range(n):
	d[l[i]] += 1
	d1[d[l[i]]] += 1
	if d[l[i]] * d1[d[l[i]]] == i + 1 and i != n - 1:
		ans = i + 1
		continue
	if d[l[i]] * d1[d[l[i]]] == i:
		ans = i
print(ans + 1)


from collections import defaultdict

def go():
	n = int(input())
	a = [int(i) for i in input().split(' ')]
	count = defaultdict(int)
	f = defaultdict(int)
	m = 0
	answer = 0
	for i in range(1, n + 1):
		color = a[i - 1]
		count[f[color]] -= 1
		f[color] += 1
		count[f[color]] += 1
		m = max(m, f[color])
		ok = False
		if count[1] == i:
			ok = True
		elif count[i] == 1:
			ok = True
		elif count[1] == 1 and count[m] * m == i - 1:
			ok = True
		elif count[m - 1] * (m - 1) == i - m and count[m] == 1:
			ok = True
		if ok:
			answer = i
	return answer
print(go())


n = int(input())
u = [int(u) for u in input().split()]
NMAX = 100005
suma = [0 for _ in range(NMAX)]
total = [0 for _ in range(NMAX)]
diferentes = 0
sol = 0
maximo = 1
for (i, v) in enumerate(u):
	if total[v] == 0:
		diferentes += 1
	else:
		suma[total[v]] -= 1
	total[v] += 1
	suma[total[v]] += 1
	maximo = max(maximo, total[v])
	if diferentes <= 1:
		sol = i
	if suma[maximo - 1] == diferentes - 1 and suma[maximo] == 1:
		sol = i
	if suma[maximo] == diferentes - 1 and suma[1] == 1:
		sol = i
	if suma[1] == diferentes:
		sol = i
print(sol + 1)


import sys
input = sys.stdin.readline
from collections import defaultdict as dd
n = int(input())
u = list(map(int, input().split()))
c = dd(int)
cc = dd(int)
for uu in u:
	c[uu] += 1
for x in c:
	cc[c[x]] += 1
for uu in reversed(u):
	if len(cc) == 2:
		(aa, bb) = sorted(list(cc.items()))
		(k1, v1) = aa
		(k2, v2) = bb
		if k2 - k1 == 1 and v2 == 1 or (k1 == 1 and v1 == 1):
			print(n)
			exit()
	elif len(cc) == 1:
		(aa,) = list(cc.items())
		(k1, v1) = aa
		if k1 == 1 or v1 == 1:
			print(n)
			exit()
	cc[c[uu]] -= 1
	if cc[c[uu]] == 0:
		del cc[c[uu]]
	c[uu] -= 1
	if c[uu] == 0:
		del c[uu]
	if c[uu]:
		cc[c[uu]] += 1
	n -= 1


n = int(input())
a = list(map(lambda x: int(x), input().split()))
freq_map = {}
freq = {}
maximum = 0
for i in range(0, len(a)):
	if a[i] not in freq:
		freq[a[i]] = 0
	freq[a[i]] += 1
	if len(freq_map) > 0:
		if freq[a[i]] - 1 in freq_map:
			freq_map[freq[a[i]] - 1] -= 1
			if freq_map[freq[a[i]] - 1] == 0:
				del freq_map[freq[a[i]] - 1]
		if freq[a[i]] not in freq_map:
			freq_map[freq[a[i]]] = 0
		freq_map[freq[a[i]]] += 1
	else:
		freq_map[freq[a[i]]] = 1
	if len(freq_map) == 1:
		key = list(freq_map.keys())[0]
		if key == 1:
			maximum = i + 1
		if key > 1 and freq_map[key] == 1:
			maximum = i + 1
	if len(freq_map) == 2 and 1 in list(freq_map.values()):
		keys = list(freq_map.keys())
		values = list(freq_map.values())
		if 1 in keys and freq_map[1] == 1:
			maximum = i + 1
		if keys[0] - keys[1] == 1 and freq_map[keys[1]] >= freq_map[keys[0]] or (keys[1] - keys[0] == 1 and freq_map[keys[0]] >= freq_map[keys[1]]):
			maximum = i + 1
print(maximum)


import sys
from math import gcd
import bisect
import heapq
from collections import deque
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 998244353
cntcol = [0] * (10 ** 5 + 1)
cntcnt = [0] * (10 ** 5 + 1)
maxx = 0
n = int(ri())
a = Ri()
ans = -1
for i in range(len(a)):
	flag = False
	cntcnt[cntcol[a[i]]] -= 1
	cntcol[a[i]] += 1
	cntcnt[cntcol[a[i]]] += 1
	maxx = max(maxx, cntcol[a[i]])
	if cntcnt[1] == i + 1:
		flag = True
	elif cntcnt[i + 1] == 1:
		flag = True
	elif cntcnt[maxx] * maxx == i and cntcnt[1] == 1:
		flag = True
	elif cntcnt[maxx - 1] * (maxx - 1) == i + 1 - maxx and cntcnt[maxx] == 1:
		flag = True
	if flag:
		ans = i + 1
print(ans)


n = int(input())
a = [int(x) for x in input().split()]
counter = [0] * 10 ** 5
how = [0] * (10 ** 5 + 1)
answer = big = 0
for i in range(n):
	counter[a[i] - 1] += 1
	big = max(big, counter[a[i] - 1])
	how[counter[a[i] - 1]] += 1
	how[counter[a[i] - 1] - 1] -= 1
	if how[1] == i + 1:
		answer = i + 1
	elif how[big] == 1 and how[big - 1] * (big - 1) == i + 1 - big:
		answer = i + 1
	elif how[big] == 1 and big == i + 1:
		answer = i + 1
	elif how[1] == 1 and how[big] * big == i:
		answer = i + 1
print(answer)


from sys import stdin, stdout, exit
from collections import defaultdict
from heapq import *
n = int(input())
a = list(map(int, stdin.readline().split()))
N = 10 ** 5 + 2
bit = [0] * (N + 1)

def query(i):
	ans = 0
	while i > 0:
		ans += bit[i]
		i -= i & -i
	return ans

def update(i, x):
	while i <= N:
		bit[i] += x
		i += i & -i

def smallest():
	lo = 0
	hi = N
	while lo + 1 < hi:
		mid = (lo + hi + 1) // 2
		if query(mid) > 0:
			hi = mid
		else:
			lo = mid
	return hi

def largest():
	lo = 1
	hi = N + 1
	total = query(N)
	while lo + 1 < hi:
		mid = (lo + hi) // 2
		if query(mid - 1) < total:
			lo = mid
		else:
			hi = mid
	return lo

def valid():
	sm = smallest()
	ct_sm = query(sm) - query(sm - 1)
	lg = largest()
	ct_lg = query(lg) - query(lg - 1)
	total = query(N)
	if total == 1 or (ct_sm == total - 1 and lg == sm + 1):
		return True
	if sm == 1 and ct_lg >= total - 1:
		return True
	return False
cts = defaultdict(int)
for i in range(n):
	cts[a[i]] += 1
for (_, c) in cts.items():
	update(c, 1)
for i in range(n - 1, -1, -1):
	if valid():
		print(i + 1)
		exit()
	old_ct = cts[a[i]]
	cts[a[i]] -= 1
	update(old_ct, -1)
	if old_ct > 1:
		update(old_ct - 1, +1)


n = int(input())
A = list(map(int, input().split()))
B = [n] + [0] * (n + 1)
C = {}
calcset = set()
good = 0
next = 0
for i in range(n):
	C[A[i]] = C.get(A[i], 0) + 1
	B[C[A[i]] - 1] -= 1
	B[C[A[i]]] += 1
	if C[A[i]] > next:
		next = C[A[i]]
	calcset.add(A[i])
	if B[next] + B[next - 1] == len(calcset) and B[next] == 1 or (B[1] == 1 and B[next] == len(calcset) - 1) or (next == 1 and B[next] == len(calcset)):
		good = max(good, i)
print(good + 1)


from collections import Counter
n = int(input())
u = map(int, input().split())
r = 0
d = {}
c = Counter()
m = 0
for (i, ui) in enumerate(u, 1):
	if c[ui] in d:
		d[c[ui]] -= 1
	c[ui] += 1
	if c[ui] not in d:
		d[c[ui]] = 0
		m = c[ui]
	d[c[ui]] += 1
	if d[m] == 1 and m * d[m] == i:
		r = i
	elif d[1] == i:
		r = i
	elif d.get(1, 0) == 1 and d[m] * m == i - 1:
		r = i
	elif d[m] == 1 and d[m - 1] * (m - 1) == i - m:
		r = i
print(r)


def main():
	from sys import stdin, stdout

	def read():
		return stdin.readline().rstrip('\n')

	def read_array(sep=None, maxsplit=-1):
		return read().split(sep, maxsplit)

	def read_int():
		return int(read())

	def read_int_array(sep=None, maxsplit=-1):
		return [int(a) for a in read_array(sep, maxsplit)]

	def write(*args, **kwargs):
		sep = kwargs.get('sep', ' ')
		end = kwargs.get('end', '\n')
		stdout.write(sep.join((str(a) for a in args)) + end)

	def write_array(array, **kwargs):
		sep = kwargs.get('sep', ' ')
		end = kwargs.get('end', '\n')
		stdout.write(sep.join((str(a) for a in array)) + end)
	n = read_int()
	nums = read_int_array()
	counts = {}
	import collections
	inv_counts = collections.defaultdict(int)
	out = 0
	for (i, x) in enumerate(nums):
		c = inv_counts[x]
		if c:
			counts[c].remove(x)
			if not counts[c]:
				counts.pop(c)
		c += 1
		inv_counts[x] = c
		counts.setdefault(c, set()).add(x)
		if len(counts) == 2 and any((len(s) == 1 and (k - 1 in counts or k == 1) for (k, s) in list(counts.items()))):
			out = i + 1
		elif len(counts) == 1:
			k = next(iter(list(counts.keys())))
			if k == 1 or len(counts[k]) == 1:
				out = i + 1
	write(out)
main()


n = int(input())
l = list(map(int, input().split()))
m = [0 for i in range(10 ** 5 + 5)]
wyn = 0
duz = [0 for i in range(10 ** 5 + 5)]
ile = [0 for i in range(10 ** 5 + 5)]
zajete = 0
praw = []
jedynki = 0
mini = 100000000000
maksi = -100000000000000000
for i in range(n):
	if m[l[i]] == 1:
		jedynki -= 1
	if m[l[i]] == 0:
		zajete += 1
		jedynki += 1
	ile[m[l[i]]] -= 1
	m[l[i]] += 1
	ile[m[l[i]]] += 1
	maksi = max(m[l[i]], maksi)
	if jedynki > 1:
		if zajete == jedynki or (zajete == jedynki + 1 and maksi == 2):
			wyn = i + 1
	if jedynki == 1:
		if i + 1 == zajete * maksi - maksi + 1:
			wyn = i + 1
	if jedynki == 0:
		if ile[maksi - 1] == zajete - 1:
			wyn = i + 1
print(wyn)


import collections
import itertools
from functools import reduce
mod = 10 ** 9 + 7

def permutationbysum():
	for _ in range(int(input())):
		(num, l, r, achieve) = map(int, input().split())
		k = r - l + 1
		if k * (k + 1) // 2 <= achieve <= k * (num * 2 + 1 - k) // 2:
			outpos = r % num
			inpos = l - 1
			ans = [0] * num
			for i in range(num, 0, -1):
				if achieve - i > 0 or (achieve - i == 0 and inpos == r - 1):
					achieve -= i
					ans[inpos] = i
					inpos += 1
				else:
					ans[outpos] = i
					outpos += 1
					outpos %= num
			print(*ans)
		else:
			print(-1)

def peaks():
	for _ in range(int(input())):
		(num, peak) = map(int, input().split())
		pos = 1
		rpos = num
		ans = []
		now = 0
		if num == 1:
			if not peak:
				print(1)
			else:
				print(-1)
			continue
		if num == 2:
			if peak:
				print(-1)
			else:
				print(1, 2)
			continue
		added = 0
		while rpos + 1 != pos:
			if not peak:
				while pos <= rpos:
					ans.append(pos)
					pos += 1
				break
			if not now:
				ans.append(pos)
				pos += 1
			else:
				ans.append(rpos)
				rpos -= 1
				if num - added != 1:
					peak -= 1
			added += 1
			now = 1 - now
		if peak:
			print(-1)
			continue
		print(*ans)
import sys
input = sys.stdin.readline

def addone():
	for _ in range(int(input())):
		(num, changes) = input().split()
		l = collections.deque(sorted([int(i) for i in num]))
		perm = collections.deque()
		changes = int(changes)
		cd = 0
		ans = len(num)
		while True:
			nextnum = l.pop()
			while perm and perm[-1] == nextnum:
				l.append(perm.pop())
			c = 10 - nextnum - cd
			changes -= c
			cd += c
			if changes >= 0:
				if not c:
					perm.appendleft(1 - cd)
					l.appendleft(-cd)
				else:
					l.appendleft(1 - cd)
					l.appendleft(-cd)
				ans += 1
			else:
				break
		print(ans % 1000000007)
import math

def andsequences():

	def mapping(num):
		nonlocal mnum
		nonlocal c
		num = int(num)
		if num < mnum:
			mnum = num
			c = 1
		elif num == mnum:
			c += 1
		return num
	mod = 1000000007
	for _ in range(int(input())):
		mnum = float('inf')
		c = 0
		num = int(input())
		l = list(map(mapping, input().split()))
		for i in l:
			if mnum & i != mnum:
				print(0)
				break
		else:
			if c == 1:
				print(0)
			else:
				print(math.factorial(num - 2) * (c - 1) * c % mod)

def numberdigit():
	n = 10 ** 5 * 2
	l = [0] * 11
	mod = 10 ** 9 + 7
	l[0] = l[1] = l[2] = l[3] = l[4] = l[5] = l[6] = l[7] = l[8] = 2
	l[9] = 3
	l[10] = 4
	for i in range(11, n):
		l.append((l[i - 10] + l[i - 9]) % mod)
	for _ in range(int(input())):
		(num, c) = input().split()
		c = int(c)
		ans = 0
		for i in num:
			i = int(i)
			if 10 - i > c:
				ans += 1
			else:
				ans += l[c - (10 - i)]
		print(ans % mod)

def mushroom():
	(people, t1, t2, percent) = map(int, input().split())
	l = []
	percent = 1 - percent * 0.01
	for i in range(1, people + 1):
		(s, s1) = map(int, input().split())
		l.append([i, max(s * t1 * percent + s1 * t2, s1 * t1 * percent + s * t2)])
	l.sort(key=lambda x: x[1], reverse=True)
	for i in l:
		i[1] = '{:.2f}'.format(i[1])
		print(*i)

def escape():
	prins = int(input())
	dra = int(input())
	start = int(input())
	pack = int(input())
	c = int(input())
	speeddiff = dra - prins
	if speeddiff <= 0:
		return 0
	pd = start * prins
	ans = 0
	while pd < c:
		hs = pd / speeddiff
		pd += prins * hs
		if pd >= c:
			break
		time = pd / dra
		time += pack
		pd += prins * time
		ans += 1
	return ans

def perm():

	def high(n, k):
		return k * (2 * n - k + 1) // 2

	def low(k):
		return k * (k + 1) // 2
	for _ in range(int(input())):
		(num, lef, rig, s) = map(int, input().split())
		k = rig - lef + 1
		(rig, lef) = (rig - 1, lef - 1)
		if not high(num, k) >= s >= low(k):
			print(-1)
			continue
		l = [0] * num
		lp = lef
		rp = lef - 1
		for i in range(num, 0, -1):
			if high(i, k) >= s and s - i >= low(k - 1) and k:
				l[lp] = i
				lp += 1
				s -= i
				k -= 1
			else:
				l[rp] = i
				rp -= 1
		if k:
			print(-1)
		else:
			print(*l)

def newcom():
	for _ in range(int(input())):
		(days, price) = map(int, input().split())
		dl = input().split()
		worth = input().split()
		worth.append(0)
		ans = float('inf')
		req = 0
		left = 0
		for i in range(days):
			a = int(dl[i])
			w = int(worth[i])
			ans = min(ans, req + max(0, price - left + a - 1) // a)
			ns = max(0, w - left + a - 1) // a
			req += ns + 1
			left += a * ns - w
		print(ans)

def perfectsq():
	for _ in range(int(input())):
		n = input()
		for i in input().split():
			sq = math.sqrt(int(i))
			if sq != int(sq):
				print('YES')
				break
		else:
			print('NO')

def and0big():
	for _ in range(int(input())):
		(l, k) = map(int, input().split())
		print(l ** k % mod)
import math

def mod1p():
	n = int(input())
	ans = dict()
	p = 1
	for i in range(1, n):
		if math.gcd(i, n) == 1:
			ans[str(i)] = True
			p = p * i % n
	if p == 1:
		print(len(ans))
		print(' '.join(ans.keys()))
	else:
		ans.pop(str(p))
		print(len(ans))
		print(' '.join(ans.keys()))

def shorttask():
	num = 10000100
	l = [-1] * (num + 2)
	s = [-1] * (num + 2)
	l[1] = 1
	for i in range(2, int(math.sqrt(num + 1)) + 2):
		if l[i] == -1:
			l[i] = i
			for x in range(i * i, num + 1, i):
				if l[x] == -1:
					l[x] = i
	s[1] = 1
	for i in range(2, num + 1):
		if l[i] == -1:
			l[i] = i
			s[i] = i + 1
		else:
			i1 = i
			s[i] = 1
			while i1 % l[i] == 0:
				i1 //= l[i]
				s[i] = s[i] * l[i] + 1
			s[i] *= s[i1]
	ans = [-1] * (num + 1)
	for i in range(num, 0, -1):
		if s[i] < num:
			ans[s[i]] = i
	for _ in range(int(input())):
		print(ans[int(input())])

def review():
	for _ in range(int(input())):
		n = int(input())
		ans = 0
		for i in input().split():
			i = int(i)
			if i == 1 or i == 3:
				ans += 1
		print(ans)

def GCDleng():
	po10 = [0] * 11
	po10[1] = 1
	for i in range(2, 11):
		po10[i] = po10[i - 1] * 10
	for _ in range(int(input())):
		(n, n1, res) = map(int, input().split())
		print(po10[n], po10[n1] + po10[res])

def anothercarddeck():
	(n, q) = map(int, input().split())
	l = input().split()
	d = {l[i]: i for i in range(n - 1, -1, -1)}
	ans = []
	for i in input().split():
		now = d[i]
		ans.append(now + 1)
		for key in d:
			if d[key] < now:
				d[key] += 1
		d[i] = 0
	print(*ans)

def mincoststring():
	(n, letters) = map(int, input().split())
	l = [chr(i + 97) for i in range(letters)]
	ans = []
	real = letters - 1
	if not n:
		print(*ans, sep='')
		return
	if n == 1:
		print(*ans, sep='', end='')
		print(l[1 % (real + 1)])
		return
	while n:
		for i in range(len(l)):
			for i1 in range(i, len(l)):
				if i1 != real:
					ans.append(l[i1])
					ans.append(l[i])
					n -= 2
				else:
					ans.append(l[i1])
					n -= 1
				if not n:
					print(*ans, sep='')
					return
				if n == 1:
					print(*ans, sep='', end='')
					print(l[(i1 + 1) % (real + 1)])
					return
	print(*ans)

def mincost2():
	(n, letters) = map(int, input().split())
	l = [chr(i + 97) for i in range(letters)]
	comb = []
	if letters == 1 or n == 1:
		print('a' * n)
		return
	for i in range(letters):
		for i1 in range(i, letters):
			comb.append(l[i1] + l[i])
	lc = len(comb)
	while True:
		for i in range(lc):
			if ord(comb[i][0]) - 97 == letters - 1:
				n -= 1
				print(comb[i][0], end='')
			else:
				n -= 2
				print(comb[i], end='')
			if n == 1:
				pos = ord(comb[i][0]) - 97 + 1
				print(l[pos % letters])
				return
			if not n:
				return

def Tittat():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		l = list(map(int, input().split()))
		for i in range(n):
			if not k:
				break
			while k and l[i]:
				l[i] -= 1
				l[-1] += 1
				k -= 1
		print(*l)

def xorq2():
	for _ in range(int(input())):
		n = int(input())
		s = 0
		num = -1
		nc = 0
		c = 0
		for i in input().split():
			i = int(i)
			s ^= i
			c += 1
			if num == -1 and s == i:
				num = s
				s = 0
				nc += c
				c = 0
			if num != -1 and (s == num or not s):
				s = 0
				nc += c
				c = 0
		print(['NO', 'YES'][nc == n])

def xorq2re():
	n = int(input())
	s = input().split()
	xor = 0
	for i in range(n):
		s[i] = int(s[i])
		xor ^= s[i]
	if not xor:
		print('YES')
	else:
		new = 0
		ans = 0
		for i in s:
			new ^= i
			if new == xor:
				new = 0
				ans += 1
		print(['NO', 'YES'][ans > 1])
import sys
sys.setrecursionlimit(2300)

def q3partition():

	def partition():
		if tol % 2:
			return 0
		up = tol
		rec = [[False] * (up + 2) for _ in range(n + 1)]
		rec[0][0] = True
		for i in range(1, n + 1):
			v = l[i - 1]
			for j in range(up + 1):
				if rec[i - 1][j]:
					if v + j <= up:
						rec[i][j + v] = True
					rec[i][j] = True
		return rec[n][tol // 2]

	def ints(x):
		nonlocal tol
		nonlocal gcf
		x = int(x)
		tol += x
		gcf = math.gcd(gcf, x) if gcf != float('inf') else x
		return x
	n = int(input())
	tol = 0
	gcf = float('inf')
	l = list(map(ints, input().split()))
	if partition():
		pos = 1
		for i in l:
			if i // gcf % 2:
				print(1)
				print(pos)
				return
			pos += 1
	else:
		print(0)

def permu(n, r):
	return math.factorial(n) // math.factorial(n - r)

def comb(n, r):
	return math.factorial(n) // math.factorial(r) * math.factorial(n - r)

def calc():
	n = int(input())
	ans = permu(n, n)
	for i in range(1, n + 1):
		ans -= comb(n, i)
	print(ans)

def order():
	for _ in range(int(input())):
		n = int(input())
		odd = []
		even = []
		for i in input().split():
			i = int(i)
			if i % 2:
				odd.append(i)
			else:
				even.append(i)
		print(*odd + even)

def TMTdoc():
	n = int(input())
	l = input().rstrip()
	tts = 0
	tms = 0
	for i in l:
		if i == 'T':
			tts += 1
		else:
			tms += 1
	if tms * 2 == tts:
		nowts = 0
		nowms = 0
		for i in l:
			if i == 'T':
				nowts += 1
			else:
				nowms += 1
				if nowts >= nowms and tms - nowms + 1 <= tts - nowts:
					continue
				return 'NO'
	else:
		return 'NO'
	return 'YES'

def relayrace():

	def solve(n):
		if n:
			s = -1
		else:
			s = 1
		nowmax = -float('inf')
		nowmin = -nowmax
		ans = 0
		for (i, v) in sorted(l, key=lambda x: (x[1], s * int(x[0])), reverse=True):
			i = int(i)
			if i > nowmax:
				nowmax = i
			if i < nowmin:
				nowmin = i
			ans += v * (nowmax - nowmin)
		return ans
	n = int(input())
	l = -1
	ans = 0
	for i in sorted(input().split(), key=lambda x: int(x)):
		if l == -1:
			l = int(i)
		else:
			ans += int(i) - l
	return ans

def relayraces():
	n = int(input())
	l = sorted(map(int, input().split()))
	minv = float('INF')
	minpos = 0
	for i in range(len(l)):
		if i > 0 and 0 <= l[i] - l[i - 1] <= minv:
			minv = l[i] - l[i - 1]
			minpos = i
		if i < n - 1 and l[i + 1] - l[i] <= minv:
			minv = l[i + 1] - l[i]
			minpos = i
	lpos = minpos - 1
	rpos = minpos + 1
	ans = 0
	while lpos >= 0 and rpos < n:
		diffl = -(l[lpos] - l[minpos])
		diffr = l[rpos] - l[minpos]
		if diffl < diffr:
			minpos = lpos
			lpos -= 1
			ans += diffl
		else:
			minpos = rpos
			rpos += 1
			ans += diffr
	if lpos < 0:
		m = l[0]
		for i in range(rpos, n):
			ans += l[i] - m
	else:
		h = l[-1]
		for i in range(minpos, -1, -1):
			ans += h - l[i]
	return ans

def relayracess():

	def recur(l, r):
		if l == r:
			return 0
		if d[l, r] != -1:
			return d[l, r]
		ans = nums[r] - nums[l] + min(recur(l + 1, r), recur(l, r - 1))
		d[l, r] = ans
		return ans
	d = collections.defaultdict(lambda : -1)
	n = int(input())
	nums = sorted(map(int, input().split()))
	return recur(0, n - 1)

def relayracesss():
	n = int(input())
	l = sorted(map(int, input().split()))
	dp = [[0] * n for _ in range(n)]
	for i in range(n - 2, -1, -1):
		for i1 in range(i + 1, n):
			dp[i][i1] = l[i1] - l[i] + min(dp[i + 1][i1], dp[i][i1 - 1])
	return dp[0][n - 1]

def relayracessss():
	n = int(input())
	l = sorted(map(int, input().split()))
	dp = [0] * n
	for le in range(n - 2, -1, -1):
		for ri in range(le + 1, n):
			dp[ri] = l[ri] - l[le] + min(dp[ri], dp[ri - 1])
	return dp[-1]

def binli():
	n = int(input())
	n2 = n * 2
	s = input().rstrip()
	s1 = input().rstrip()
	s2 = input().rstrip()
	posl = [0, 0, 0]
	ans = ''
	while max(posl) < n2:
		l = [[], []]
		l[int(s[posl[0]])].append(0)
		l[int(s1[posl[1]])].append(1)
		l[int(s2[posl[2]])].append(2)
		if len(l[0]) >= 2:
			for i in l[0]:
				posl[i] += 1
			ans += '0'
		else:
			for i in l[1]:
				posl[i] += 1
			ans += '1'
	if posl[0] == n2:
		if posl[1] >= posl[2]:
			ans += s1[posl[1]:]
		else:
			ans += s2[posl[2]:]
	elif posl[1] == n2:
		if posl[0] >= posl[2]:
			ans += s[posl[0]:]
		else:
			ans += s2[posl[2]:]
	elif posl[0] >= posl[1]:
		ans += s[posl[0]:]
	else:
		ans += s1[posl[1]:]
	print(ans)

def almostsort():
	(n, k) = map(int, input().split())
	ul = 2 ** (n - 1)
	if k > ul:
		return [-1]
	permen = []
	bi = bin(k - 1)[2:]
	if bi == '0':
		return range(1, n + 1)
	pos = n - len(bi)
	ans = list(range(1, pos))
	for i in bi:
		permen.append(pos)
		if not int(i):
			ans += permen[::-1]
			permen = []
		pos += 1
	permen.append(n)
	ans += permen[::-1]
	return ans

def q1_2050():
	for i in range(int(input())):
		s = int(input())
		if s % 2050:
			print(-1)
		else:
			ab = 2050
			while ab <= s:
				ab *= 10
			ab //= 10
			c = 0
			while s and s != 1:
				c += s // ab
				s = s % ab
				while s != 1 and s and (s < ab):
					ab //= 10
			print(c)

def q2jog():
	(n, m) = map(int, input().split())
	sortbyval = []
	rowsv = [collections.defaultdict(int) for _ in range(n)]
	for row in range(n):
		for i in input().split():
			i = int(i)
			sortbyval.append([i, row])
			rowsv[row][i] += 1
	sortbyval.sort(key=lambda x: x[0])
	larl = []
	for i in range(0, n * m, m):
		larl.append(sortbyval[i:i + m])
	ans = [[0] * m for _ in range(n)]
	person = 0
	for i in larl:
		for (v, pos) in i:
			ans[pos][person] = v
			rowsv[pos][v] -= 1
			person += 1
			if person == m:
				break
		else:
			continue
		break
	for r in range(n):
		for c in range(m):
			if not ans[r][c]:
				for key in list(rowsv[r].keys()):
					if not rowsv[r][key]:
						rowsv[r].pop(key)
						continue
					rowsv[r][key] -= 1
					ans[r][c] = key
					break
	for i in ans:
		print(*i)

def q3fillomino(n, inp):

	def gorow():
		nonlocal nowp
		nonlocal col
		nonlocal totake
		t = 0
		if nowp and col < n and totake and (not l[col][nowp - 1]):
			for back in range(nowp, -1, -1):
				if l[col][back]:
					nowp += 1
					col += 1
					return t
				if not totake:
					return t
				l[col][back] = i
				totake -= 1
				nowp -= 1
				t = 1
			nowp += 1
			col += 1
		return t
	l = [[0] * i for i in range(1, n + 1)]
	p = 0
	for i in inp:
		totake = int(i)
		nowp = p
		col = p
		while col < n:
			if not totake:
				break
			for _ in range(n - p):
				if not gorow():
					break
			if not totake or col == n or nowp == n:
				break
			l[col][nowp] = i
			totake -= 1
			col += 1
		p += 1
	for i in l:
		print(*i)

def q3fillominoclear(n, inp):
	l = [[0] * i for i in range(1, n + 1)]
	p = 0
	for i in inp:
		take = int(i) - 1
		l[p][p] = i
		(x, y) = (p, p)
		while take:
			if y and (not l[x][y - 1]):
				y -= 1
			else:
				x += 1
			l[x][y] = i
			take -= 1
		p += 1
	for i in l:
		print(*i)

def q4explor():

	def gen(r, c):
		res = float('inf')
		if r:
			res = min(res, his[r - 1][c] + 2 * colstep[r - 1][c])
		if r < rows - 1:
			res = min(res, his[r + 1][c] + 2 * colstep[r][c])
		if c:
			res = min(res, his[r][c - 1] + 2 * rowstep[r][c - 1])
		if c < cols - 1:
			res = min(res, his[r][c + 1] + 2 * rowstep[r][c])
		return res
	(rows, cols, k) = map(int, input().split())
	if k % 2:
		for i in range(rows):
			print(*[-1] * cols)
		return
	rowstep = [list(map(int, input().split())) for _ in range(rows)]
	colstep = [list(map(int, input().split())) for _ in range(rows - 1)]
	his = [[0] * cols for _ in range(rows)]
	for _ in range(k // 2):
		temp = [[gen(r, c) for c in range(cols)] for r in range(rows)]
		his = temp
	for i in his:
		print(*i)

def cvacations():

	def de(v):
		nonlocal last
		if v == 2:
			last = 2
		elif v == 1:
			last = 1
	n = int(input())
	ans = 0
	last = 0
	l = input().split()
	for i1 in range(n):
		i = int(l[i1])
		if not i:
			last = 0
			ans += 1
			continue
		if i == 1:
			if last != 2:
				last = 2
				continue
			ans += 1
			last = 0
		elif i == 2:
			if last != 1:
				last = 1
				continue
			ans += 1
			last = 0
		elif not last:
			if i1 < n - 1:
				de(int(l[i1 + 1]))
				if int(l[i1 + 1]) == 3:
					for pos in range(i1 + 2, n):
						if l[pos] != 3:
							r = l[pos]
							break
					else:
						last = 1
						continue
					de(r)
			else:
				break
		elif last == 1:
			last = 2
		elif last == 2:
			last = 1
	return ans

def brackets():
	s = input().rstrip()
	(lpos, rpos) = (0, len(s) - 1)
	ans = []
	while lpos + 1 <= rpos:
		if s[lpos] == '(':
			if s[rpos] == ')':
				ans.append(lpos + 1)
				ans.append(rpos + 1)
				lpos += 1
				rpos -= 1
			else:
				rpos -= 1
		else:
			lpos += 1
	if ans:
		print(1)
		print(len(ans))
		print(*sorted(ans))
	else:
		print(0)

def In():
	return map(int, input().split())

def complibook():
	(n, q) = In()
	nums = list(In())
	for _ in range(q):
		(l, r, x) = In()
		num = nums[x - 1]
		les = 0
		for i in range(l - 1, r):
			if nums[i] < num:
				les += 1
		print(['No', 'Yes'][les + l - 1 == x - 1])

def bstr():
	for _ in range(int(input())):
		(n, k) = In()
		now = 1
		times = 2
		while k > now:
			k -= now
			now += 1
			times += 1
		fir = n - times
		sec = n - k
		for i in range(n):
			if i == fir or i == sec:
				print('b', end='')
			else:
				print('a', end='')
		print()

def avgsuper():
	(n, k, oper) = In()
	l = sorted(In(), reverse=True)
	nowavg = sum(l) / n
	(addpos, addnum) = (0, 0)
	for i in range(oper):
		if n == 1 and addpos != 0:
			break
		new = (nowavg * n - l[n - 1]) / max(n - 1, 1)
		if 1 / n > new - nowavg and addpos < n:
			addnum += 1
			if addnum >= k:
				addpos += 1
				addnum = 0
			nowavg += 1 / n
		else:
			nowavg = new
			n -= 1
	print(nowavg)

def avgsuper2():
	(n, k, oper) = In()
	l = sorted(In(), reverse=True)
	prefix = [0] * (n + 1)
	for i in range(1, n + 1):
		prefix[i] = l[i - 1] + prefix[i - 1]
	prefix.pop(0)
	ans = 0
	for i in range(n - 1, max(-1, n - oper - 2), -1):
		ans = max(ans, (prefix[i] + min(k * (i + 1), oper - (n - i - 1))) / (i + 1))
	return ans

def tanna():
	(n, k, A, B) = (int(input()), int(input()), int(input()), int(input()))
	if k == 1:
		return (n - 1) * A
	x = n
	ans = 0
	while x != 1:
		if x < k:
			return ans + A * (x - 1)
		if not x % k:
			nexts = x // k
			ans += min(B, A * (x - nexts))
			x = nexts
		else:
			new = x % k
			ans += new * A
			x = x - new
	return ans

def segsqu():
	square = 1
	num = int(input())
	while num > square * square:
		square += 1
	cols = square
	rows = math.ceil(num / cols)
	print(cols + rows)

def ParallelUniverses():
	(n, k, m, t) = In()
	for _ in range(t):
		(sta, pos) = In()
		if sta:
			n += 1
			if pos - 1 < k:
				k += 1
		elif pos < k:
			k -= pos
			n -= pos
		else:
			n = pos
		print(n, k)

def treasure():
	num = int(input())
	choose = max((list(In()) for _ in range(num)))
	ch2 = min((list(In()) for _ in range(num)))
	print(choose[0] + ch2[0], choose[1] + ch2[1])

def tradingbus():
	(plan, m, cap) = In()
	l = []
	for _ in range(plan):
		name = input()
		l.append([list(In()) for _ in range(m)])
	ans = 0
	for i in range(plan):
		fix = l[i]
		for i1 in range(i + 1, plan):
			fix1 = l[i1]
			sellnew = []
			buynew = []
			for x in range(m):
				fnow = fix[x]
				f1now = fix1[x]
				sellnew.append([max(f1now[1] - fnow[0], 0), fnow[2]])
				buynew.append([max(fnow[1] - f1now[0], 0), f1now[2]])
			sellnew.sort(reverse=True)
			buynew.sort(reverse=True)
			sellc = cap
			buyc = cap
			sa = 0
			ba = 0
			for x in range(m):
				left = sellnew[x][1]
				if left > sellc:
					sa += sellnew[x][0] * sellc
					break
				else:
					sa += sellnew[x][0] * left
					sellc -= left
			for x in range(m):
				left = buynew[x][1]
				if left > buyc:
					ba += buynew[x][0] * buyc
					break
				else:
					ba += buynew[x][0] * left
					buyc -= left
			ans = max(ans, max(ba, sa))
	return ans

def catparty():
	n = int(input())
	colors = [0] * 10
	appeared = 0
	ans = 0
	pos = 1
	for i in In():
		if not colors[i - 1]:
			appeared += 1
		colors[i - 1] += 1
		for x in range(10):
			if colors[x]:
				l1 = colors[:]
				l1[x] -= 1
				l1 = set(l1)
				if 0 not in l1:
					if len(l1) == 1:
						ans = pos
						break
				elif len(l1) == 2 or len(l1) == 1:
					ans = pos
					break
		pos += 1
	return ans

def catpartyhard():
	maxn = int(100000.0 + 10)
	n = int(input())
	colors = [0] * maxn
	count = [0] * maxn
	pos = 1
	mx = 0
	ans = 0
	for i in input().split():
		i = int(i)
		ok = False
		count[colors[i]] -= 1
		colors[i] += 1
		count[colors[i]] += 1
		mx = max(colors[i], mx)
		if count[1] == pos:
			ok = 1
		elif count[pos] == 1:
			ok = 1
		elif count[mx] * mx == pos - 1 and count[1] == 1:
			ok = 1
		elif count[mx - 1] * (mx - 1) == pos - mx and count[mx] == 1:
			ok = 1
		if ok:
			ans = pos
		pos += 1
	return ans
print(catpartyhard())


n = int(input())
l = [int(x) for x in input().split()]
count = [0] * (100000 + 1)
ct_colors = [0] * (n + 1)
maximum = 0
ans = 0
for i in range(n):
	a = l[i]
	ct_colors[count[a]] -= 1
	count[a] += 1
	ct_colors[count[a]] += 1
	maximum = max(maximum, count[a])
	if ct_colors[1] == i + 1:
		ans = i + 1
	elif ct_colors[i + 1] == 1:
		ans = i + 1
	elif ct_colors[1] == 1 and ct_colors[maximum] * maximum == i:
		ans = i + 1
	elif ct_colors[maximum - 1] * (maximum - 1) == i - maximum + 1 and ct_colors[maximum] == 1:
		ans = i + 1
print(ans)


n = int(input())
a = list(map(int, input().split()))
mem = {}
mark = [0 for _ in range(100001)]
max_step = 0
c = 0
for v in a:
	c += 1
	word2 = str(mark[v])
	mark[v] += 1
	word = str(mark[v])
	mem[word] = mem.setdefault(word, 0) + 1
	if word2 != '0':
		if mem.get(word2) == 1:
			del mem[word2]
		else:
			mem[word2] -= 1
	if len(mem) == 1 and '1' in mem:
		max_step = c
	elif len(mem) == 1:
		for (k, v) in mem.items():
			if v == 1:
				max_step = c
	elif len(mem) == 2:
		temp = []
		for (k, v) in mem.items():
			temp.append([int(k), v])
			if k == '1' and v == 1:
				max_step = c
		if max_step != c:
			temp.sort()
			if temp[1][0] - temp[0][0] == 1 and temp[1][1] == 1:
				max_step = c
print(max_step)


from collections import defaultdict
import sys
input = sys.stdin.readline
n = int(input())
u = [int(i) for i in input().split() if i != '\n']
(freq, freq2) = (defaultdict(int), defaultdict(int))
for i in u:
	freq[i] += 1
for j in freq:
	freq2[freq[j]] += 1
	ok = True
i = len(u) - 1
while i > -1:
	if len(freq2) == 2:
		(aa, bb) = sorted(list(freq2.items()))
		(k1, v1) = aa
		(k2, v2) = bb
		if k2 - k1 == 1 and v2 == 1 or (k1 == 1 and v1 == 1):
			print(i + 1)
			sys.exit()
	elif len(freq2) == 1:
		if len(set(u)) == 1 or set(freq.values()) == {1}:
			print(i + 1)
			exit()
	freq2[freq[u[i]]] -= 1
	if freq2[freq[u[i]]] == 0:
		del freq2[freq[u[i]]]
	freq[u[i]] -= 1
	if freq[u[i]] == 0:
		del freq[u[i]]
	if freq[u[i]]:
		freq2[freq[u[i]]] += 1
	i -= 1


n = int(input())
A = list(map(int, input().split()))
f = [0] * int(100000.0 + 1)
cnt = [0] * int(100000.0 + 1)
mx = 0
max_idx = 0
valid = False
for i in range(1, len(A) + 1):
	a = A[i - 1]
	cnt[f[a]] -= 1
	f[a] += 1
	cnt[f[a]] += 1
	mx = max(mx, f[a])
	if cnt[1] == i:
		valid = True
	elif cnt[i] == 1:
		valid = True
	elif cnt[1] == 1 and cnt[mx] * mx == i - 1:
		valid = True
	elif cnt[mx] == 1 and cnt[mx - 1] * (mx - 1) == i - mx:
		valid = True
	else:
		valid = False
	if valid:
		max_idx = i
print(max_idx)


n = int(input())
a = [int(x) for x in input().split()]
arr = [0] * 100001
freqs = [0] * 100001
freqs[0] = n
(minf, maxf) = (0, 0)
for (ind, i) in enumerate(a):
	arr[i] += 1
	freqs[arr[i]] += 1
	freqs[arr[i] - 1] -= 1
	if not freqs[arr[i] - 1] and minf == arr[i] - 1:
		minf += 1
	maxf = max(maxf, arr[i])
	if maxf == 1 or (freqs[maxf] + freqs[0] == n - 1 and freqs[1] == 1) or (freqs[maxf] == 1 and freqs[maxf - 1] + freqs[0] == n - 1):
		best = ind + 1
print(best)