This problem is same as the next one, but has smaller 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$) — 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 2 5 4 1

Output
5
Input
1
10

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
Tags: Data structures

Implementation


Solutions:
from collections import defaultdict as dd
n = int(input())
l = list(map(int, input().strip().split()))
nmfr = [0] * 100001
ocfr = [0] * 100001
(nmfr[0], ocfr[0]) = (0, 0)
setb = 0
(mnb, mxb) = (1, 1)
strk = 0
for (ind, i) in enumerate(l):
	nmfr[i] += 1
	ocfr[nmfr[i]] += 1
	ocfr[nmfr[i] - 1] -= 1
	if ocfr[nmfr[i]] == 1:
		setb += 1
	if ocfr[nmfr[i] - 1] == 0:
		setb -= 1
		if mnb == nmfr[i] - 1:
			mnb += 1
	mnb = min(mnb, nmfr[i])
	mxb = max(mxb, nmfr[i])
	if mxb == mnb and ocfr[mxb] == 1 or mxb == mnb == 1 or (mxb - mnb == 1 and ocfr[mxb] == 1) or (setb == 2 and ocfr[mnb] == mnb == 1):
		strk = ind + 1
print(strk)


import sys

def is_party_time(d):
	for item in d.keys():
		sub_d = d.copy()
		sub_d[item] -= 1
		if sub_d[item] == 0:
			del sub_d[item]
		if len(set(sub_d.values())) <= 1:
			return True
	return False

def cat_party_house(n, a):
	result = None
	d = dict()
	for (idx, item) in enumerate(a):
		if d.get(item) is None:
			d[item] = 1
		else:
			d[item] += 1
		if is_party_time(d):
			result = idx
	return result + 1
n = int(input())
a = [int(item) for item in input().split()]
print(cat_party_house(n, a))


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)


def get_num():
	return int(input())

def print_arr(arr: list):
	for val in arr:
		print(val)

def read_num_list():
	num_str = input()
	return [int(v) for v in num_str.split(' ')]

def read_nums(k):
	lst = []
	for _ in range(k):
		lst.append(get_num())
	return lst
n = get_num()
colors = read_num_list()

def is_streak(counts: dict) -> bool:
	count_len = len(counts)
	if count_len == 1:
		k = list(counts.keys())[0]
		if k == 1 or len(counts[k]) == 1:
			return True
		else:
			return False
	elif count_len == 2:
		(k1, k2) = sorted(list(counts.keys()))
		if not (len(counts[k1]) == 1 or len(counts[k2])):
			return False
		if k2 - k1 == 1 and len(counts[k2]) == 1 or (k1 == 1 and len(counts[1]) == 1):
			return True
		else:
			return False
	else:
		return False
if n <= 2:
	print(n)
else:
	streak = -1
	possible_colors = set(range(1, 11))
	seen = {c: 0 for c in possible_colors}
	inverted_seen = {}
	for (i, color) in enumerate(colors):
		prev_count = seen[color]
		new_count = prev_count + 1
		seen[color] = new_count
		if prev_count != 0:
			inverted_seen[prev_count].remove(color)
			if len(inverted_seen[prev_count]) == 0:
				inverted_seen.pop(prev_count)
		if new_count not in inverted_seen:
			inverted_seen[new_count] = set()
		inverted_seen[new_count].add(color)
		if is_streak(inverted_seen):
			streak = i + 1
	print(max(streak, 2))


n = int(input())
l = list(map(int, input().split()))
m = [0 for i in range(11)]
varr = 0
for i in range(n):
	m[l[i]] += 1
	listt = [m[i] for i in range(11) if m[i] != 0]
	listt = sorted(listt)
	if len(listt) == 1:
		varr = i + 1
	if len(listt) > 1:
		if listt[0] == 1 and sum(listt) == 1 + len(listt) * listt[1] - listt[1]:
			varr = i + 1
		elif listt[0] == listt[-2] and listt[-1] == listt[0] + 1:
			varr = i + 1
print(varr)


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)


n = int(input())
temp = list(map(int, input().split()))
x = 0
hold = [0] * 20
hold[temp[0]] = 1
for j in range(1, n):
	hold[temp[j]] = hold[temp[j]] + 1
	anmol = set(hold)
	if len(anmol) == 2:
		anmol = sorted(anmol)
		t = anmol[1] + anmol[0]
		if 1 in anmol:
			x = j
		elif hold.count(t) == 1:
			x = j
	elif len(anmol) == 3:
		diksha = sorted(anmol)
		if hold.count(1) == 1 and diksha[1] == 1:
			x = j
		elif hold.count(diksha[2]) == 1 and diksha[2] - diksha[1] == 1:
			x = j
print(x + 1)


n = int(input())
a = list(map(int, input().split()))
p = [[0] * 10 for i in range(n + 1)]
for i in range(1, n + 1):
	p[i][a[i - 1] - 1] += 1
	for j in range(10):
		p[i][j] += p[i - 1][j]
for i in range(n, 0, -1):
	k = set(p[i])
	if 0 in k:
		k.remove(0)
	if len(k) == 2:
		if p[i].count(max(k)) == 1 and min(k) == max(k) - 1:
			print(i)
			break
		if p[i].count(min(k)) == 1 and min(k) == 1:
			print(i)
			break
	elif len(k) == 1:
		m = k.pop()
		if m == 1:
			print(i)
			break
		if p[i].count(m) == 1:
			print(i)
			break


n = int(input())
l1 = list(map(int, input().split()))
d1 = {}
d2 = {}
total = 0
l2 = [0] * 10
i = 0
ans = 1
for item in l1:
	i += 1
	l2[item - 1] += 1
	x = sum(l2)
	y = 10 - l2.count(0)
	if (x - 1) % y == 0:
		z = (x - 1) // y
	else:
		z = -1
	if y > 1 and (x - 1) % (y - 1) == 0:
		f = (x - 1) // (y - 1)
	else:
		f = -1
	c1 = 0
	c2 = 0
	if z == -1 and f == -1:
		continue
	for item in l2:
		if item != 0:
			if z != -1 and item == z:
				c1 += 1
			if f != -1 and item == f:
				c2 += 1
	if c1 == y - 1 or c2 == y - 1:
		ans = i
	if z == 1:
		if c1 == y:
			ans = i
	if f == 1:
		if c2 == y:
			ans = i
print(ans)


n = int(input())
u = map(int, input().split())
max_x = 1
counts = [0] * 10 ** 5
first_u = next(u)
counts[first_u - 1] = 1
count_counts = {1: 1}
for (i, v) in enumerate(u):
	v -= 1
	counts[v] += 1
	if counts[v] > 1:
		count_counts[counts[v] - 1] -= 1
		if count_counts[counts[v] - 1] == 0:
			del count_counts[counts[v] - 1]
	if counts[v] in count_counts:
		count_counts[counts[v]] += 1
	else:
		count_counts[counts[v]] = 1
	if len(count_counts) == 2:
		(a, b) = sorted(count_counts.keys())
		if b == a + 1 and count_counts[b] == 1 or (a == 1 and count_counts[a] == 1):
			max_x = i + 2
	elif len(count_counts) == 1:
		a = next(iter(count_counts.keys()))
		if a == 1 or count_counts[a] == 1:
			max_x = i + 2
print(max_x)


from collections import defaultdict as dd
n = int(input())
l = list(map(int, input().strip().split()))
d = dd(int)
mx = 1
for i in range(n):
	d[l[i]] += 1
	l1 = list(d.values())
	if len(d) == 1 or (len(set(l1)) == 2 and (max(l1) - min(l1) == 1 and l1.count(max(l1)) == 1 or (min(l1) == 1 and l1.count(1) == 1))) or (len(set(l1)) == 1 and l1[0] == 1):
		mx = i + 1
print(mx)


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)


n = int(input())
ans = 0
a = list(map(int, input().split()))
count = [0] * 10
k = 0
for each in a:
	k += 1
	count[each - 1] += 1
	f = [k for k in count if k > 0]
	fmin = min(f)
	fmax = max(f)
	(lf, lsf) = (len(f), len(set(f)))
	if lsf > 2:
		continue
	if lf == 1:
		ans = k
	elif fmax - fmin == 1 and f.count(fmax) == 1:
		ans = k
	elif fmax == fmin == 1:
		ans = k
	elif fmin == 1 and f.count(fmin) == 1:
		ans = k
print(n if not ans else ans)


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 collections import Counter
n = int(input())
us = list(map(int, input().split()))
counter = Counter()

def satisfy():
	value = None
	outlier = None
	keys = list(counter.keys())
	if len(keys) == 1:
		return True
	if len(keys) == 2:
		if counter[keys[0]] == 1:
			return True
		if counter[keys[1]] == 1:
			return True
		if abs(counter[keys[1]] - counter[keys[0]]) == 1:
			return True
		return False
	(a, b, c) = [counter[i] for i in keys[:3]]
	if a == b:
		value = a
		if a != c:
			outlier = c
	elif a == c:
		value = a
		if a != b:
			outlier = b
	elif b == c:
		value = b
		if a != b:
			outlier = a
	else:
		return False
	for c in keys[3:]:
		if counter[c] == value:
			continue
		if not outlier:
			outlier = counter[c]
		else:
			return False
	if not outlier:
		if value == 1:
			return True
		else:
			return False
	if outlier - 1 == value:
		return True
	if outlier == 1:
		return True
	return False
found = None
for (i, u) in enumerate(us):
	counter[u] += 1
	if satisfy():
		found = i
if found:
	print(found + 1)
else:
	print(1)


from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 7)

def iin():
	return int(stdin.readline())

def lin():
	return list(map(int, stdin.readline().split()))

def main():
	from collections import defaultdict
	n = iin()
	a = lin()
	dc = {}
	count = defaultdict(int)
	ans = -1
	for (i, j) in enumerate(a):
		pv = count[j]
		count[j] += 1
		nw = count[j]
		if pv:
			dc[pv] -= 1
		if nw in dc:
			dc[nw] += 1
		else:
			dc[nw] = 1
		if pv and dc[pv] == 0:
			dc.pop(pv)
		l = len(dc)
		if l <= 2:
			for mn in dc:
				d1 = dc.copy()
				d1[mn] -= 1
				if d1[mn] == 0:
					d1.pop(mn)
				if mn - 1 > 0:
					if mn - 1 in d1:
						d1[mn - 1] += 1
					else:
						d1[mn - 1] = 1
				l = len(d1)
				if l <= 1:
					ans = i + 1
	print(ans)
main()


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)


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))
n = inp()
a = list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
ma = []
ma_del = []
mi = []
mi_del = []
cnt = [0] * (10 ** 5 + 10)
kind = set()
res = 0
for (i, x) in enumerate(a):
	if cnt[x] > 0:
		heappush(ma_del, -cnt[x])
		heappush(mi_del, cnt[x])
	cnt[x] += 1
	kind.add(x)
	heappush(ma, -cnt[x])
	heappush(mi, cnt[x])
	while ma and ma_del:
		if ma[0] == ma_del[0]:
			heappop(ma)
			heappop(ma_del)
		else:
			break
	while mi and mi_del:
		if mi[0] == mi_del[0]:
			heappop(mi)
			heappop(mi_del)
		else:
			break
	MA = -ma[0]
	MI = mi[0]
	K = len(kind)
	if MA - MI == 1 and MA + (K - 1) * MI == i + 1 or (MI == 1 and MA * (K - 1) + MI == i + 1) or MA == MI == 1 or (K == 1):
		res = i + 1
print(res)


from collections import Counter as co
n = int(input())
a = list(map(int, input().split()))
d = dict(co(a))
for i in range(1, n + 1):
	x = list(d.values())
	y = set(x)
	l = len(y)
	if len(x) == 1:
		print(n - i + 1)
		exit()
	elif l == 1 and y.pop() == 1:
		print(n - i + 1)
		exit()
	elif l == 2 and x.count(1) == 1:
		print(n - i + 1)
		exit()
	elif l == 2 and x.count(max(y)) == 1 and (abs(y.pop() - y.pop()) == 1):
		print(n - i + 1)
		exit()
	elif d[a[-i]] != 1:
		d[a[-i]] -= 1
	else:
		d.pop(a[-i])


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)


n = int(input())
a = list(map(int, input().split()))

def ok(pos):
	freq = list(filter(lambda x: x, count[pos]))
	if len(freq) == 1:
		return True
	s = set(freq)
	if len(s) == 1:
		return freq[0] == 1
	if len(s) > 2:
		return False
	(_min, _max) = sorted(s)
	return _max - _min == 1 and freq.count(_max) == 1 or (_min == 1 and freq.count(_min) == 1)
count = [[0 for _ in range(11)] for _ in range(n)]
for i in range(n):
	count[i] = count[i - 1][:]
	count[i][a[i]] += 1
for i in range(n - 1, -1, -1):
	if ok(i):
		print(i + 1)
		exit()


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)


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)


from sys import stdin, stdout
stdin.readline

def mp():
	return list(map(int, stdin.readline().strip().split()))

def it():
	return int(stdin.readline().strip())
from collections import defaultdict as dd, Counter as C, deque
from math import ceil, gcd, sqrt, factorial, log2, floor
n = it()
l = mp()
v = [0] * 10
ans = 0
for i in range(n):
	v[l[i] - 1] += 1
	x = [i for i in v if i]
	x.sort()
	if len(x) == 1 or (x[0] == x[-2] and x[-1] == x[-2] + 1) or (x[1] == x[-1] and x[0] == 1):
		ans = i + 1
print(ans)


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)


n = int(input())
u = list(map(int, input().split()))
colour = [0] * (10 ** 5 + 1)
count = [0] * (10 ** 5 + 1)
x = 1
max_c = 0
for i in range(1, n + 1):
	if count[colour[u[i - 1]]]:
		count[colour[u[i - 1]]] = count[colour[u[i - 1]]] - 1
	colour[u[i - 1]] += 1
	count[colour[u[i - 1]]] += 1
	max_c = max(max_c, colour[u[i - 1]])
	if count[max_c] == 1 and (max_c - 1) * count[max_c - 1] + max_c - 1 == i - 1:
		x = i
	elif count[i] == i:
		x = i
	elif count[1] == 1 and max_c * count[max_c] == i - 1:
		x = i
	elif count[1] == i:
		x = i
print(x)


import sys
input = sys.stdin.readline
from math import log2, log, ceil

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def nCr(n, k):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return res

def upper_bound(a, x, lo=0):
	hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if a[mid] < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def primefs(n):
	primes = {}
	while n % 2 == 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

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 swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	while x != link[x]:
		x = link[x]
	return x

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(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
MAXN = int(1000000.0 + 5)
import os
import sys
from io import BytesIO, IOBase
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')

def find_parent(parent, i, cnt):
	cnt += 1
	if parent[i - 1] == i:
		return cnt
	if parent[i - 1] != i:
		find_parent(parent, parent[i - 1], cnt)
from collections import Counter
from collections import Counter
import math
from bisect import bisect_right

def can(s):
	cnt = 0
	for i in d:
		if d[i] == s:
			cnt += 1
	if cnt == 1:
		return 1
	else:
		return 0
n = int(input())
arr = list(map(int, input().split()))
c = Counter(arr)
cnt = 0
d = {}
ans = 0
for i in range(n):
	if arr[i] not in d:
		cnt += 1
		d[arr[i]] = 1
	else:
		d[arr[i]] += 1
	val = list(set(d.values()))
	if cnt == 1:
		ans = max(ans, i + 1)
	elif len(val) == 1 and val[0] == 1:
		ans = max(ans, i + 1)
	elif len(val) == 2 and can(max(val[0], val[1])) and (abs(val[0] - val[1]) == 1):
		ans = max(ans, i + 1)
	elif len(val) == 2 and can(1):
		ans = max(ans, i + 1)
print(ans)


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():
	n = int(input())
	colors = [0] * 10
	count = [0] * n
	pos = 1
	mx = 0
	ans = 0
	for i in In():
		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[i] == 1:
			ok = 1
		elif count[mx] * mx == pos - 1:
			ok = 1
		elif count[mx - 1] * (mx - 1) == pos - 1 and count[mx] == 1:
			ok = 1
		if ok:
			ans = pos
	return ans
print(catparty())


n = int(input())
num = [0] + list(map(int, input().split()))
(a, b) = ({}, {})
res = 1
for i in range(1, n + 1):
	x = num[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:
		res = i + 1
	if a[x] * b[a[x]] == i - 1:
		res = i
print(res)


import sys, os
from io import BytesIO, IOBase
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, 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')
(stdin, stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

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

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

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b
S1 = 'abcdefghijklmnopqrstuvwxyz'
S2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
n = iinp()
arr = lmp()
cnt = l1d(10)
ans = 1
for (k, i) in enumerate(arr):
	cnt[i - 1] += 1
	x = set(cnt)
	if 0 in x:
		x.remove(0)
	if x == {1} or (len(x) == 1 and cnt.count(x.pop()) == 1):
		ans = k + 1
	if len(x) == 2:
		a = x.pop()
		b = x.pop()
		if cnt.count(a) == 1 and (a - b == 1 or a == 1) or (cnt.count(b) == 1 and (b - a == 1 or b == 1)):
			ans = k + 1
print(ans)


input()
(a, b) = ({}, {})
r = i = 0
for u in input().split():
	i += 1
	c = a.get(u, 0)
	if c:
		b[c] -= 1
		if b[c] == 0:
			del b[c]
	c += 1
	a[u] = c
	b[c] = b.get(c, 0) + 1
	l = len(b)
	if l == next(iter(b)) == 1 or len(a) == 1:
		r = i
	if l == 2:
		(x, y) = sorted(b)
		if x == b[x] == 1 or y - x == b[y] == 1:
			r = i
print(r)


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)


from sys import setcheckinterval, stdin, setrecursionlimit
setcheckinterval(1000)
setrecursionlimit(10 ** 6)
iin = lambda : int(stdin.readline())
lin = lambda : list(map(int, stdin.readline().split()))
n = iin()
a = lin()
a = [i - 1 for i in a]
sol = [[0 for i in range(10)] for i in range(n)]
for i in range(n):
	sol[i][a[i]] += 1
for i in range(1, n):
	for j in range(10):
		sol[i][j] += sol[i - 1][j]
for i in range(n - 1, -1, -1):
	ans = {}
	for j in sol[i]:
		if j == 0:
			continue
		try:
			ans[j] += 1
		except:
			ans[j] = 1
	l = len(ans)
	if l == 1:
		if ans[list(ans.keys())[0]] != 1 and list(ans.keys())[0] != 1:
			continue
		print(i + 1)
		exit()
	elif l == 2:
		a1 = sorted(ans.keys(), key=lambda x: ans[x])
		if ans[a1[0]] != 1:
			continue
		if a1[0] == 1 or (a1[1] > a1[0] and ans[a1[1]] == 1 and (a1[0] == a1[1] - 1)):
			print(i + 1)
			exit()
		else:
			if a1[1] < a1[0] and a1[0] - 1 == a1[1]:
				print(i + 1)
				exit()
			continue
	else:
		continue


a = int(input())
from collections import *
al = {}
count = [0 for i in range(pow(10, 5) + 1)]
z = list(map(int, input().split()))
dl = defaultdict(int)
maxa = 0
for i in range(len(z)):
	count[z[i]] += 1
	if i == 0:
		al[1] = 1
		dl[1] = 1
	else:
		if dl[count[z[i]]] == 0:
			al[count[z[i]]] = 1
			dl[count[z[i]]] = 1
		else:
			al[count[z[i]]] += 1
		m = count[z[i]]
		m -= 1
		if m > 0:
			al[m] -= 1
			if al[m] == 0:
				dl[m] = 0
				del al[m]
	temp = []
	if len(al) == 2:
		for j in al:
			temp.append([j, al[j]])
		if temp[1][0] == 1 and temp[1][1] == 1:
			maxa = max(maxa, i + 1)
		if temp[0][0] == 1 and temp[0][1] == 1:
			maxa = max(maxa, i + 1)
		if temp[1][0] == temp[0][0] + 1 and temp[1][1] == 1:
			maxa = max(maxa, i + 1)
		if temp[0][0] == temp[1][0] + 1 and temp[0][1] == 1:
			maxa = max(maxa, i + 1)
	if len(al) == 1:
		for j in al:
			temp.append([j, al[j]])
		if temp[0][1] == 1 or temp[0][0] == 1:
			maxa = max(maxa, i + 1)
print(maxa)


def task(line1, line2):
	from collections import defaultdict
	n = int(line1)
	u = list(map(int, line2.split(' ')))
	ud = defaultdict(lambda : 0)
	for ui in u:
		ud[ui] += 1
	res = n
	for ui in reversed(u):
		keys = list(ud.values())
		s_keys = set(keys)
		if len(s_keys) == 2:
			if max(keys) - min(keys) == 1 and keys.count(max(keys)) == 1 or keys.count(1) == 1:
				break
		if s_keys == {1}:
			break
		if len(keys) == 1:
			break
		if ud[ui] == 1:
			del ud[ui]
		else:
			ud[ui] -= 1
		res -= 1
	return res
print(task(input(), input()))


from collections import defaultdict

def solve():
	N = int(input())
	A = [int(k) for k in input().split()]
	freq = defaultdict(int)
	ans = N
	for i in range(N):
		freq[A[i]] += 1
		s = list(freq.values())
		n = len(s)
		maxs = max(s)
		mins = min(s)
		mx = s.count(maxs)
		mn = n - mx
		if len(set(s)) == 2 and (mx == 1 and (maxs == 1 or maxs - mins == 1)) or (mn == 1 and (mins == 1 or mins - maxs == 1)):
			ans = i + 1
	print(min(ans, N))
solve()


def check(cnt):
	cnt_vals = {}
	nz_cnt = 0
	for c in cnt:
		if c > 0:
			nz_cnt += 1
			if c not in cnt_vals:
				cnt_vals[c] = 1
			else:
				cnt_vals[c] += 1
	if nz_cnt == 1:
		return True
	if len(cnt_vals) == 1 and 1 in cnt_vals:
		return True
	if len(cnt_vals) > 2:
		return False
	if 1 in cnt_vals and cnt_vals[1] == 1:
		return True
	keys = list(cnt_vals.keys())
	if max(keys) == min(keys) + 1 and cnt_vals[max(keys)] == 1:
		return True
	return False
n = int(input())
colors = input().split()
colors = [int(k) - 1 for k in colors]
cnt = [0 for _ in range(10)]
ans = 0
for i in range(n):
	cnt[colors[i]] += 1
	mn = min(cnt)
	mx_found = False
	uniq_found = False
	is_valid = True
	if check(cnt):
		ans = i + 1
print(ans)


import sys
n = int(input())
nums = list(map(int, input().split()))
eleCount = {}
possibleMax = 1
for i in range(n):
	if nums[i] in eleCount.keys():
		eleCount[nums[i]] += 1
		if len(eleCount.keys()) == 1:
			possibleMax = i + 1
		else:
			x = list(eleCount.values())
			x.sort()
			if x[0] == 1 and x[-1] == 1:
				possibleMax = i + 1
			elif x[0] == 1 and x[1] != 1:
				if len(set(x[1:])) == 1:
					possibleMax = i + 1
			else:
				x[-1] = x[-1] - 1
				if len(set(x)) == 1:
					possibleMax = i + 1
	else:
		eleCount[nums[i]] = 1
		if len(eleCount.keys()) == 1:
			possibleMax = i + 1
		else:
			x = list(eleCount.values())
			x.sort()
			if x[0] == 1 and x[-1] == 1:
				possibleMax = i + 1
			elif x[0] == 1 and x[1] != 1:
				if len(set(x[1:])) == 1:
					possibleMax = i + 1
			else:
				x[-1] = x[-1] - 1
				if len(set(x)) == 1:
					possibleMax = i + 1
print(possibleMax)


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)


MAX = 100000
n = int(input())
a = list(map(int, input().split()))

def ok():
	if len(uniques) == 1:
		return True
	if len(freqs) == 1:
		return maxFreq == 1
	if len(freqs) > 2:
		return False
	return maxFreq - minFreq == 1 and freqs[maxFreq] == 1 or (minFreq == 1 and freqs[minFreq] == 1)
uniques = set()
count = [0] * (MAX + 1)
freqs = {}
maxFreq = 0
minFreq = 1 << 30
ret = 0
for (i, val) in enumerate(a):
	uniques.add(val)
	count[val] += 1
	curFreq = count[val]
	freqs.setdefault(curFreq - 1, 1)
	freqs[curFreq - 1] -= 1
	if freqs[curFreq - 1] == 0:
		freqs.pop(curFreq - 1)
	freqs.setdefault(curFreq, 0)
	freqs[curFreq] += 1
	maxFreq = max(maxFreq, curFreq)
	minFreq = min(freqs.keys())
	if ok():
		ret = i
print(ret + 1)


n = int(input())
u = [int(x) for x in input().split()]
cnt = {}
for x in u:
	cnt[x] = cnt.get(x, 0) + 1
cnt2 = {}
for v in cnt.values():
	cnt2[v] = cnt2.get(v, 0) + 1
k = len(u)
while True:
	if len(cnt2) == 1:
		if list(cnt2.values())[0] == 1 or list(cnt2.keys())[0] == 1:
			print(k)
			break
	if len(cnt2) == 2:
		[k1, k2] = list(cnt2.keys())
		if abs(k1 - k2) == 1:
			mk = max(k1, k2)
			if cnt2[mk] == 1:
				print(k)
				break
		if min(k1, k2) == 1 and cnt2[1] == 1:
			print(k)
			break
	x = u[k - 1]
	cnt2[cnt[x]] -= 1
	if cnt2[cnt[x]] == 0:
		del cnt2[cnt[x]]
	cnt[x] -= 1
	if cnt[x] == 0:
		del cnt[x]
	else:
		cnt2[cnt[x]] = cnt2.get(cnt[x], 0) + 1
	k -= 1


n = int(input())
L = [int(i) for i in input().split()]
D = {}

def check(D):
	G = list(D.values())
	G = list(reversed(sorted(G)))
	f = len(G) - 1
	if f == 0:
		return 1
	elif G[0] == G[1] + 1 == G[f] + 1:
		return 1
	elif G[0] == G[f - 1] and G[f] == 1:
		return 1
	else:
		return 0
for i in L:
	if i in D:
		D[i] += 1
	else:
		D[i] = 1
for i in range(n - 1, -1, -1):
	t = 0
	t = check(D)
	if t or i == 0:
		print(i + 1)
		break
	else:
		D[L[i]] -= 1
	if D[L[i]] == 0:
		del D[L[i]]


import sys
allnums = (int(x) for x in sys.stdin.readlines()[1].split())
maxx = 0
counts = [0 for i in range(0, 10)]

def isok():
	global counts
	nonzeroes = [c for c in counts if c != 0]
	if len(nonzeroes) == 1:
		return True
	if any((x == 1 for x in nonzeroes)):
		s = sum(nonzeroes)
		n = len(nonzeroes) - 1
		base = (s - 1) // n
		if sum([x for x in nonzeroes if x != base]) <= 1:
			return True
	if any((x != 1 for x in nonzeroes)):
		s = sum(nonzeroes)
		n = len(nonzeroes)
		base = s // n
		if any((x < base or x > base + 1 for x in nonzeroes)):
			return False
		if s == n * base + 1:
			return True
	return False
for (i, num) in enumerate(allnums):
	counts[num - 1] += 1
	if isok():
		maxx = i + 1
print(f'{maxx}')


n = int(input())
u = list(map(int, input().split()))
true = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
big = 1
for i in range(n):
	true[u[i] - 1] += 1
	vals = set(true)
	try:
		vals.remove(0)
	except:
		pass
	if len(vals) == 2 and 1 in vals and (true.count(1) == 1):
		big = max(big, i + 1)
	elif len(vals) == 1 and 1 in vals:
		big = max(big, i + 1)
	elif len(vals) == 1 and true.count(max(vals)) == 1:
		big = max(big, i + 1)
	elif len(vals) == 2:
		a = max(vals)
		if true.count(a) == 1 and min(vals) == a - 1:
			big = max(big, i + 1)
print(big)


n = int(input())
arr = list(map(int, input().split()))
count = [0] * 10
ans = 1
for i in range(n):
	count[arr[i] - 1] += 1
	cp_count = list.copy(count)
	cp_count.sort()
	r = 0
	for j in range(1, 10):
		if cp_count[j] != cp_count[j - 1]:
			r += 1
	if r == 0 and cp_count[0] == 1:
		ans = i + 1
	elif r == 1:
		li = []
		qw = [0, 0]
		for k in range(10):
			if (cp_count[k] in li) == False:
				li.append(cp_count[k])
			qw[li.index(cp_count[k])] += 1
		if li[0] == 0 and qw[1] == 1:
			ans = i + 1
		elif li[0] == 0 and li[1] == 1:
			ans = i + 1
		elif li[1] - li[0] == 1 and qw[1] == 1:
			ans = i + 1
		elif li[0] == 1 and qw[0] == 1:
			ans = i + 1
	elif r == 2:
		li = []
		qw = [0, 0, 0]
		for k in range(10):
			if (cp_count[k] in li) == False:
				li.append(cp_count[k])
			qw[li.index(cp_count[k])] += 1
		if li[0] == 0 and li[2] - li[1] == 1 and (qw[2] == 1):
			ans = i + 1
		elif li[1] == 1 and qw[1] == 1:
			ans = i + 1
print(ans)


def gns():
	return [int(x) for x in input().split()]

def gn():
	return int(input())
n = gn()
ns = gns()
cl = {}
nn = {}
ans = -1
i = 0
for c in ns:
	i += 1
	if i == 2:
		xxxx = 0
	if c in cl:
		cl[c] += 1
	else:
		cl[c] = 1
	t = cl[c]
	if t in nn:
		nn[t] += 1
	else:
		nn[t] = 1
	if t != 1:
		nn[t - 1] -= 1
		if nn[t - 1] == 0:
			nn.pop(t - 1)
	if len(nn) > 2:
		continue
	elif len(nn) == 1:
		if list(nn.values())[0] == 1 or list(nn.keys())[0] == 1:
			ans = i
	else:
		tem = list(nn.keys())
		tem.sort()
		(s, l) = tem
		if s == 1 and nn[s] == 1:
			ans = i
			continue
		if nn[l] == 1 and l - s == 1:
			ans = i
			continue
print(ans)


n = int(input())
a = [int(s) for s in input().split()]
b = []
c = []
x = 1
for i in range(n):
	if a[i] not in b:
		b.append(a[i])
		c.append(1)
	else:
		for j in range(len(b)):
			if b[j] == a[i]:
				c[j] += 1
	count = 0
	k = 0
	lenb = len(b)
	if lenb > 5 and ((i - 1) // lenb or (i - 1) // (lenb - 1)) or lenb <= 5:
		for j in range(lenb):
			k += c[j]
		for j in range(1, lenb):
			d = [] + c
			if c[j] == 1:
				del d[j]
				if d == [(k - 1) // (lenb - 1)] * (lenb - 1):
					x = i + 1
		if (k - 1) % lenb == 0:
			for q in range(lenb):
				c[q] -= 1
				if c == [(k - 1) // lenb] * lenb:
					x = i + 1
				c[q] += 1
	else:
		continue
print(x)


(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())
u = [int(x) for x in input().split()]
colors = [0 for _ in range(10)]
streak = 1

def check1(d):
	c = [d[i] for i in range(10)]
	a = max(c)
	f1 = False
	for i in range(10):
		if c[i] == 1:
			c[i] = 0
			f1 = True
			break
	if not f1:
		return False
	diff = 0
	for e in c:
		if e != a and e != 0:
			diff += 1
	return diff == 0

def check(d):
	c = [d[i] for i in range(10)]
	index = 0
	a = c[0]
	for i in range(1, 10):
		if a < c[i]:
			index = i
			a = c[i]
	c[index] -= 1
	a -= 1
	diff = 0
	for e in c:
		if e != a and e != 0:
			diff += 1
	return diff == 0
for i in range(n):
	colors[u[i] - 1] += 1
	if check1(colors) or check(colors):
		streak = i + 1
print(streak)


def check(c):
	d = {}
	for i in range(10):
		if c[i] != 0:
			if c[i] not in d:
				d[c[i]] = 1
			else:
				d[c[i]] += 1
	l = list(d.keys())
	if len(l) == 1 and (l[0] == 1 or (l[0] != 1 and d[l[0]] == 1)):
		return True
	elif len(l) == 2:
		if l[0] == 1 and d[l[0]] == 1 or (l[1] == 1 and d[l[1]] == 1):
			return True
		elif l[0] == l[1] + 1:
			if d[l[0]] == 1:
				return True
			else:
				return False
		elif l[1] == l[0] + 1:
			if d[l[1]] == 1:
				return True
			else:
				return False
		else:
			return False
	else:
		return False
n = int(input())
l = list(map(int, input().split()))
c = [0 for _ in range(10)]
t = 1
c[l[0] - 1] += 1
for i in range(1, n):
	c[l[i] - 1] += 1
	if check(c):
		t = i + 1
print(t)


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)


def checkEqual(array):
	while 0 in array:
		array.remove(0)
	return len(list(set(array))) == 1 or len(array) == 0

def check(dic):
	v = dic.values()
	v = list(v)
	while 0 in v:
		v.remove(0)
	v = sorted(v)
	if len(v) > 1:
		for i in range(len(v)):
			arr = [v[k] if k != i else v[k] - 1 for k in range(len(v))]
			if checkEqual(arr):
				return True
		return False
	else:
		return True
n = int(input())
array = list(map(int, input().split()))
dictionary = {i: 0 for i in range(1, 11)}
answer = 0
for x in range(len(array)):
	dictionary[array[x]] += 1
	if check(dictionary):
		answer = x + 1
print(answer)


n = int(input())
l = list(map(int, input().split()))
res = 0
c = [0] * 10
for j in range(n):
	c[l[j] - 1] += 1
	lo = [i for i in c if i]
	lo.sort()
	if len(lo) == 1 or (lo[0] == lo[-2] and lo[-1] - 1 == lo[-2]) or (lo[1] == lo[-1] and lo[0] == 1):
		res = j
print(res + 1)


n = int(input())
(a, b) = ({}, {})
r = i = 0
for u in input().split():
	i += 1
	c = a[u] = a.get(u, 0) + 1
	d = b[c] = b.get(c, 0) + c
	r = (r, d)[d in (i - (i == n), i - 1)]
print(r + 1)


n = int(input())
a = [int(x) for x in input().split()]
dic = {}
counter = 0
i = 1
for item in a:
	dic[item] = 0
for item in a:
	dic[item] += 1
	b = []
	for key in dic:
		if dic[key] > 0:
			b.append(dic[key])
	b.sort()
	if len(b) > 1:
		if b[-1] - 1 == b[-2] == b[0] or (b[0] == 1 and b[1] == b[-1]):
			counter = i
	else:
		counter = i
	i += 1
print(counter)


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())
a = list(map(int, input().split()))
c = [0] * 11
ma = 1
for i in range(n):
	c[a[i]] += 1
	for k in range(1, 11):
		if c[k] > 0:
			c[k] -= 1
			s = {}
			for j in range(1, 11):
				if c[j] > 0:
					if c[j] not in s:
						s[c[j]] = 1
					else:
						s[c[j]] += 1
			c[k] += 1
			if len(s) == 1:
				ma = max(ma, i + 1)
				break
print(ma)


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)


import copy
n = int(input())
a = list(map(int, input().split()))

def array_count(arr):
	arr_target = [[]]
	cnt = 1
	for i in range(1, len(arr)):
		if arr[i] == arr[i - 1]:
			cnt += 1
		else:
			arr_target.append([arr[i - 1], cnt])
			cnt = 1
	arr_target.append([arr[len(arr) - 1], cnt])
	del arr_target[0]
	return arr_target
color = [0] * 10
diff_arr = [0] * n
for i in range(n):
	color[a[i] - 1] += 1
	color_m = copy.deepcopy(color)
	color_m.sort()
	color_arr = array_count(color_m)
	color_fm = 0
	color_arr.sort()
	for j in range(len(color_arr)):
		if color_arr[j][1] > color_fm:
			color_fm = color_arr[j][0]
	diff = 0
	for j in range(len(color)):
		if color[j] != 0 and color[j] != color_fm:
			diff += min(color[j], abs(color[j] - color_fm))
	if diff == 0:
		temp = True
		for j in range(len(color)):
			if color[j] > 1:
				temp = False
		tt = 0
		for j in range(len(color)):
			if color[j] != 0:
				tt += 1
		if tt == 1:
			temp = True
		if temp == True:
			diff = 1
	diff_arr[i] = diff
for i in range(n):
	if diff_arr[n - i - 1] == 1:
		print(n - i)
		break
else:
	print(0)


from collections import Counter

def check(counter, curr_len, curr_color, curr_one):
	if curr_len == 1 or curr_color == 1 or curr_one == curr_len:
		return True
	if curr_one == 1:
		curr_color -= 1
	if (curr_len - 1) % curr_color != 0:
		return False
	correct_num = (curr_len - 1) // curr_color
	(false_count, false_num) = (0, 0)
	for i in range(1, 11):
		if counter[i] != correct_num and counter[i] != 0:
			false_count += 1
			false_num = counter[i]
	return false_count == 1 and (false_num - 1 == correct_num or false_count - 1 == 0)

def main():
	n = int(input())
	u = list(map(int, input().split()))
	counter = Counter()
	(max_days, curr_color, curr_one) = (0, 0, 0)
	for i in range(n):
		if counter[u[i]] == 0:
			curr_color += 1
			curr_one += 1
		if counter[u[i]] == 1:
			curr_one -= 1
		counter[u[i]] += 1
		if check(counter, i + 1, curr_color, curr_one):
			max_days = i + 1
	print(max_days)

def __starting_point():
	main()
__starting_point()


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)


import atexit
import io
import sys
_I_B = sys.stdin.read().splitlines()
input = iter(_I_B).__next__
_O_B = io.StringIO()
sys.stdout = _O_B

@atexit.register
def write():
	sys.__stdout__.write(_O_B.getvalue())

def main():
	u = [0] * 10
	n = int(input())
	a = list(map(int, input().split()))
	streak = 0
	for i in range(n):
		u[a[i] - 1] += 1
		ts = set(u)
		if 0 in ts:
			ts.remove(0)
		if len(ts) == 2:
			e1 = ts.pop()
			e2 = ts.pop()
			c1 = u.count(e1)
			c2 = u.count(e2)
			if e1 - e2 == 1 and c1 == 1 or (e2 - e1 == 1 and c2 == 1):
				streak = i + 1
			elif e1 == 1 and c1 == 1 or (e2 == 1 and c2 == 1):
				streak = i + 1
		elif len(ts) == 1:
			e = ts.pop()
			if e == 1 or u.count(e) == 1:
				streak = i + 1
	print(streak)
main()


from collections import defaultdict
n = int(input())
x = list(map(int, input().strip().split()))
s = [[0] * 10 for _ in range(n + 1)]
for i in range(n):
	for j in range(10):
		s[i + 1][j] = s[i][j]
	s[i + 1][x[i] - 1] += 1
for i in range(n, 0, -1):
	vals = defaultdict(int)
	for j in range(10):
		if s[i][j] == 0:
			continue
		vals[s[i][j]] += 1
	if len(vals) == 0:
		print(i)
		exit()
	if len(vals) == 1:
		p = list(vals.keys())[0]
		if vals[p] == 1 or p == 1:
			print(i)
			exit()
	if len(vals) == 2:
		(p, q) = sorted(vals.keys())
		if vals[1] == 1:
			print(i)
			exit()
		if q == p + 1 and vals[q] == 1:
			print(i)
			exit()


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


n = int(input())
A = list(map(int, input().split()))
ans = 1
colors = {}
for i in range(1, 11):
	colors[i] = 0
for j in range(n):
	i = A[j]
	colors[i] += 1
	q = []
	for elem in colors:
		if colors[elem]:
			q.append(colors[elem])
	q.sort()
	if len(q) == 1:
		ans = j + 1
	elif q[-1] == q[-2] + 1 and q[0] == q[-2]:
		ans = j + 1
	elif q[-1] == q[1] and q[0] == 1:
		ans = j + 1
print(ans)


def main():
	n = int(input())
	u = [int(x) for x in input().split()]
	c = [0] * 11
	ans = 0
	for i in range(n):
		c[u[i]] += 1
		f = True
		common_amount = 0
		common_occurrences = 0
		more_occurrences = 0
		one_occurrences = 0
		for j in range(1, 11):
			if c[j] > 0:
				c[j] -= 1
			else:
				continue
			common = 0
			flag = True
			for ci in c:
				if ci > 0:
					if common == 0:
						common = ci
					elif common != ci:
						flag = False
						break
			if flag:
				ans = i + 1
				c[j] += 1
				break
			c[j] += 1
	print(ans)
main()


from collections import Counter

def get_valid(d):
	cnt = dict(Counter(d.values()))
	if len(cnt) == 1 and len(d.values()) == 1:
		return True
	if 1 in cnt and (cnt[1] == 1 and len(cnt) == 2 or len(cnt) == 1):
		return True
	key = cnt.keys()
	if cnt[max(key)] == 1 and max(key) - min(key) == 1:
		return True
	return False
input()
nums = list(map(int, input().split()))
counts = dict(Counter(nums))
if len(nums) == 1:
	print(1)
else:
	for i in reversed(range(len(nums))):
		if get_valid(counts):
			print(i + 1)
			break
		counts[nums[i]] -= 1
		if counts[nums[i]] == 0:
			del counts[nums[i]]


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)


n = int(input())
u = list(map(int, input().split()))
cl = [0] * 10
cl[u[0] - 1] += 1
md = 1
for i in range(1, n):
	cc = u[i] - 1
	cl[cc] += 1
	czu = cl.count(0)
	cou = cl.count(1)
	cmu = cl.count(max(cl))
	clu = cl.count(max(cl) - 1)
	if cmu == 1 and clu == 9 - czu or (cou == 1 and cmu == 9 - czu) or cou == 10 - czu:
		md = i + 1
print(md)


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)


from collections import Counter
n = int(input())
uu = list(map(int, input().split()))
c = Counter(uu)
count = Counter(c.values())
for i in range(n, 0, -1):
	if len(count) == 1:
		(q, w) = next(iter(count.items()))
		if q == 1 or w == 1:
			break
	if len(count) == 2 and count[1] == 1:
		break
	if len(count) == 2:
		((q, qq), (w, ww)) = count.most_common()
		if q + 1 == w and ww == 1 or (w + 1 == q and qq == 1):
			break
	ui = uu[i - 1]
	count[c[ui]] -= 1
	if not count[c[ui]]:
		count.pop(c[ui])
	c[ui] -= 1
	if c[ui]:
		count[c[ui]] += 1
print(i)


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())
arr = input()
arr = [int(x) for x in arr.split(' ')]
freq = {}
f = collections.defaultdict(int)
res = 1
for i in range(N):
	num = arr[i]
	if num not in freq:
		freq[num] = 1
	else:
		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
	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
print(res)


n = int(input())
p = input().rstrip().split(' ')
l = [0] * 10
for i in range(0, len(p)):
	l[int(p[i]) - 1] += 1
	T = list(set(l))
	T.sort(key=int, reverse=True)
	if 0 in T:
		if len(T) == 2:
			if T[0] == 1:
				q = i
			elif l.count(T[0]) == 1:
				q = i
		elif len(T) == 3:
			A = T[0]
			B = T[1]
			if A == 1 and l.count(A) == 1:
				q = i
			elif B == 1 and l.count(B) == 1:
				q = i
			elif l.count(A) == 1:
				if A - 1 == B:
					q = i
	elif len(T) == 2:
		A = T[0]
		B = T[1]
		if A == 1 and l.count(A) == 1:
			q = i
		elif B == 1 and l.count(B) == 1:
			q = i
		elif l.count(A) == 1:
			if A - 1 == B:
				q = i
print(q + 1)


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')


def Maximum_Streak(a):
	counts = [0] * 11
	for (index, v) in enumerate(a):
		counts[v] += 1
		k = sorted([i for i in counts if i])
		if len(k) == 1 or (k[0] == k[-2] and k[-1] - k[-2] == 1) or (k[0] == 1 and k[1] == k[-1]):
			ans = index
	return ans + 1
n = int(input())
a = list(map(int, input().split()))
print(Maximum_Streak(a))


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


n = int(input())
u = list(map(int, input().split()))
x = [0] * 10
mx = 0
if n == 1:
	print(1)
	exit(0)
for i in range(n):
	x[u[i] - 1] += 1
	fl = False
	for j in range(10):
		x1 = x[:]
		if x1[j] != 0:
			x1[j] -= 1
			x2 = -1
			k2 = 0
			for l in x1:
				if l != 0:
					if k2 == 0 or x2 != l:
						k2 += 1
						x2 = l
			if k2 == 1:
				fl = True
	if fl:
		mx = i + 1
print(mx)


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)


n = int(input())
l = list(map(int, input().split()))
from collections import defaultdict
d = defaultdict(int)
c = defaultdict(int)
s = set([1])
x = 1
c[l[0]] = 1
d[1] = 1
for i in range(1, n):
	a = c[l[i]]
	c[l[i]] += 1
	d[a] -= 1
	d[c[l[i]]] += 1
	if d[c[l[i]]] == 1:
		s.add(c[l[i]])
	if d[a] == 0:
		s.remove(a)
	if len(s) == 2:
		l1 = list(s)
		l1.sort()
		if d[1] == 1 or (d[l1[1]] == 1 and l1[1] - l1[0] == 1):
			x = i + 1
	if len(s) == 1:
		if list(s)[0] == 1:
			x = i + 1
	if c[l[i]] == i + 1:
		x = i + 1
print(x)


n = int(input())
a = [int(i) for i in input().split()]
b = []
for i in range(11):
	b.append(0)
m = 0
b[a[0]] = 1
for i in range(1, n):
	b[a[i]] += 1
	c = set(b)
	if len(c) == 2:
		c = sorted(c)
		t = c[0] + c[1]
		if 1 in c:
			m = i
		elif b.count(t) == 1:
			m = i
	elif len(c) == 3:
		d = sorted(c)
		if d[1] == 1 and b.count(1) == 1:
			m = i
		elif d[2] - d[1] == 1 and b.count(d[2]) == 1:
			m = i
print(m + 1)


def streak(arr, l):
	x = []
	for i in arr:
		if i != 0:
			x.append(i)
	mini = min(x)
	maxi = max(x)
	mincount = x.count(mini)
	maxcount = x.count(maxi)
	if mini == 1 and mincount == l:
		return True
	elif mini == 1 and mincount == 1 and (maxi * maxcount == l - 1):
		return True
	elif mini + 1 == maxi and maxcount == 1 and (maxi * maxcount + mini * mincount == l):
		return True
	elif len(x) == 1:
		return True
	return False
n = int(input())
arr = [int(i) for i in input().split()]
arr1 = [0 for i in range(10)]
streaker = 0
for i in range(n):
	arr1[arr[i] - 1] += 1
for i in range(n - 1, -1, -1):
	if streak(arr1, i + 1):
		streaker = i + 1
		break
	arr1[arr[i] - 1] -= 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 = map(int, input().split())
c = {}
d = 0
for (i, x) in enumerate(a):
	c[x] = c.get(x, 0) + 1
	if len(c) > 1:
		if 1 in c.values():
			x = len(c) - 1
			if x and 0 == i % x:
				y = i / x
				if max(c.values()) == y:
					d = max(d, i + 1)
		if 0 == i % len(c):
			y = i / len(c)
			if min(c.values()) == y and max(c.values()) == y + 1:
				d = max(d, i + 1)
	else:
		d = max(d, i + 1)
print(d)


n = int(input())
a = list(map(int, input().split()))
dic = {i: 0 for i in range(1, 11)}
maxIndex = 0
for i in range(n):
	dic[a[i]] += 1
	flag = False
	occurence = set(dic.values()).difference({0})
	if len(occurence) > 2:
		continue
	occurence = list(occurence)
	occurence.sort()
	if len(occurence) == 1 and (occurence[0] == 1 or list(dic.values()).count(0) == 9) or (len(occurence) == 2 and (list(dic.values()).count(1) == 1 or (list(dic.values()).count(occurence[1]) == 1 and occurence[1] - occurence[0] == 1))):
		maxIndex = i
print(maxIndex + 1)


n = int(input())
array = list(map(int, input().split()))
d = [0] * 100010
v = [0] * 100010
answer = 0
m = 0
for x in range(len(array)):
	c = array[x]
	v[d[c]] -= 1
	d[c] += 1
	v[d[c]] += 1
	m = max(m, d[c])
	f = False
	if v[1] == x + 1:
		f = True
	if v[x + 1] == 1:
		f = True
	if v[1] == 1 and v[m] * m == x:
		f = True
	if v[m - 1] * (m - 1) == x + 1 - m and v[m] == 1:
		f = True
	if f:
		answer = x + 1
print(answer)


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)


NUMS = [0 for i in range(10)]

def check(nums):
	maxi = max(nums)
	category = nums.count(maxi)
	if category == 1:
		oneof = 0
		for n in nums:
			if n == maxi:
				continue
			if n == 0:
				continue
			if oneof != 0 and (n != oneof or n != maxi - 1):
				return False
			oneof = n
		return True
	elif maxi != 1:
		if nums.count(1) != 1:
			return False
		if nums.count(0) != len(nums) - category - 1:
			return False
		return True
	else:
		return True
n = int(input())
colors = list(map(int, input().split()))
res = 0
for i in range(n):
	NUMS[colors[i] - 1] += 1
	if check(NUMS):
		res = i + 1
print(res)


n = int(input())
l = [int(x) for x in input().split()]
count = [0] * (10 + 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)


ii = lambda : int(input())
kk = lambda : map(int, input().split())
k2 = lambda : map(lambda x: int(x) - 1, input().split())
ll = lambda : list(kk())
n = ii()
d = [0] * 10
maxi = 2
for (j, v) in enumerate(k2()):
	d[v] += 1
	vs = {}
	for i in range(10):
		if d[i] == 0:
			continue
		if d[i] not in vs:
			vs[d[i]] = 0
		vs[d[i]] += 1
	if len(vs) > 2:
		continue
	if len(vs) == 2:
		val = max(list(vs.keys()))
		if 1 in vs and vs[1] == 1 or (val - 1 in vs and vs[val] == 1):
			maxi = j
	elif len(vs) == 1 and (1 in vs or d.count(0) == 9):
		maxi = j
print(max(maxi + 1, min(2, n)))


from collections import defaultdict
n = int(input())
ulist = list(map(int, input().split()))
cnt = defaultdict(int)
table = defaultdict(int)
mx = 0
ans = 0
for (i, u) in enumerate(ulist, 1):
	cnt[table[u]] -= 1
	table[u] += 1
	cnt[table[u]] += 1
	mx = max(mx, table[u])
	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 and cnt[mx - 1] * (mx - 1) == i - mx:
		ok = True
	if ok:
		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)


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)


n = int(input())
arr = list(map(int, input().split()))
d = [0] * 10
max_ = 1
for i in range(n):
	d[arr[i] - 1] += 1
	lol = sorted([x for x in d if x > 0])
	kek = True
	for j in range(len(lol) - 2):
		if lol[j] != lol[j + 1]:
			kek = False
			break
	if kek and len(lol) == 1:
		max_ = max(max_, i + 1)
		continue
	elif kek and lol[-1] - 1 == lol[-2]:
		max_ = max(max_, i + 1)
		continue
	kek = True
	for j in range(1, len(lol) - 1):
		if lol[j] != lol[j + 1]:
			kek = False
			break
	if kek and lol[0] - 1 == 0:
		max_ = max(max_, i + 1)
print(max_)


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())
mark = [0 for _ in range(11)]
a = list(map(int, input().split()))
minus = 0
for v in a:
	mark[v] += 1
for v in a[::-1]:
	temp = []
	done = []
	for value in mark:
		if value != 0:
			temp.append(value)
	temp.sort()
	if temp.count(1) == 1 and (len(set(temp)) == 1 or len(set(temp)) == 2):
		print(n - minus)
		break
	temp[-1] -= 1
	if len(set(temp)) == 1 or (len(set(temp)) == 2 and 0 in temp):
		print(n - minus)
		break
	mark[v] -= 1
	minus += 1


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(input())
l = list(map(int, input().split()))
d = [0] * 10
h = 0
for i in range(n):
	d[l[i] - 1] += 1
	d1 = [] + d
	d1.sort()
	if max(d1) == 1:
		h = max(h, i + 1)
	else:
		t = 0
		for j in range(10):
			if d1[j] == 1:
				if j == 9 or d1[j + 1] == d1[9]:
					t = 1
					break
				else:
					break
		q = 0
		for j in range(10):
			if d1[j] != 0 and j == 9:
				q = 1
				break
			elif d1[j] != 0:
				if d1[j + 1] == d1[8] == d1[9] - 1 == d1[j]:
					q = 1
					break
				elif j == 8 and d1[8] == d1[9] - 1:
					q = 1
					break
				else:
					break
		if q == 1 or t == 1:
			h = max(h, i + 1)
print(h)


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)


def check(arr):
	tmp = []
	for i in arr:
		if i != 0:
			tmp.append(i)
	mi = min(tmp)
	ma = max(tmp)
	mic = tmp.count(mi)
	mac = tmp.count(ma)
	l = len(tmp)
	if mi == 1 and mic == l:
		return True
	elif mic == l - 1 and mac == 1 and (ma - mi == 1):
		return True
	elif mi == 1 and mic == 1 and (mac == l - 1):
		return True
	elif l == 1:
		return True
	else:
		return False
n = int(input())
arr = list(map(int, input().split()))
cnt = [0] * 11
for i in range(n):
	cnt[arr[i]] += 1
for i in range(n - 1, -1, -1):
	if check(cnt):
		print(i + 1)
		break
	cnt[arr[i]] -= 1


n = int(input())
otv = 1
a = list(map(int, input().split()))
kol = dict()
for i in range(n):
	o = a[i]
	if o not in kol:
		kol[o] = 1
	else:
		kol[o] += 1
	sv = set(kol.values())
	if sv == {1} or len(set(kol.keys())) == 1:
		otv = i + 1
	elif len(sv) == 2 and min(sv) == 1 and (list(kol.values()).count(min(sv)) == 1):
		otv = i + 1
	elif len(sv) == 2 and list(kol.values()).count(max(sv)) == 1 and (max(sv) - min(sv) == 1):
		otv = i + 1
print(otv)


from collections import Counter
n = int(input().strip())
arr = list(map(int, input().strip().split()))

def isValid(freq):
	freq = [i for i in freq if i]
	freq_set = sorted(list(set(freq)))
	if len(freq_set) == 1:
		return freq_set[0] == 1 or freq.count(freq_set[0]) == 1
	if len(freq_set) == 2:
		if 1 in freq_set:
			if freq.count(1) == 1:
				return True
		if freq_set[1] - freq_set[0] == 1:
			return freq.count(freq_set[1]) == 1
	return False
freq = [0] * 10
for i in arr:
	freq[i - 1] += 1
for i in range(n):
	if isValid(freq):
		print(len(arr))
		break
	freq[arr.pop(-1) - 1] -= 1


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())
a = list(map(int, input().split()))
k = set()
b = 0
ind = {}
for i in a:
	if i not in k:
		k.add(i)
		ind[i] = b
		b += 1
l = set()
occ1 = 0
ans = 1
s = [-1 for i in set(a)]
for i in range(n):
	if a[i] in l:
		j = ind[a[i]]
		s[j] += 1
	else:
		s[ind[a[i]]] = 1
		l.add(a[i])
	an = set(s) - set([-1])
	if len(an) == 2:
		p = [i for i in an]
		p1 = s.count(p[0])
		p2 = s.count(p[1])
		if p1 == 1:
			if p[0] == p[1] + 1 or p[0] == 1:
				ans = i + 1
		if p2 == 1:
			if p[1] == p[0] + 1 or p[1] == 1:
				ans = i + 1
	elif len(an) == 1:
		p = [i for i in an]
		p1 = s.count(p[0])
		if p[0] == 1 or p1 == 1:
			ans = i + 1
print(ans)


def check():
	mn = float('inf')
	mx = 0
	k = 0
	for i in mas:
		if i != 0:
			k += 1
			mx = max(mx, i)
			mn = min(mn, i)
	if mx - mn <= 1 and mas.count(mx) == 1 or (mn == 1 and k == 1 + mas.count(mx)) or mn == mx == 1:
		return True
	return False
n = int(input())
l = list(map(int, input().split()))
mas = [0] * 10
ans = 0
for i in range(n):
	mas[l[i] - 1] += 1
	if check():
		ans = i
print(ans + 1)


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 freqs_of_freqs.keys() and freqs_of_freqs[1] == 1:
			max_length = index + 2
	elif len(freqs_of_freqs) == 1:
		if 1 in freqs_of_freqs.keys() or 1 in freqs_of_freqs.values():
			max_length = index + 2
print(max_length)


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()


def main():
	n = int(input())
	colors = list(map(int, input().split()))
	dist_colors = {}
	x = 0
	for i in range(n):
		if colors[i] not in dist_colors.keys():
			dist_colors[colors[i]] = 1
		else:
			dist_colors[colors[i]] += 1
		keys = []
		for j in dist_colors.keys():
			keys.append(j)
		for j in range(len(dist_colors)):
			curr = dist_colors[keys[j]]
			dist_colors[keys[j]] -= 1
			k = 0
			while k < len(keys) and dist_colors[keys[k]] == 0:
				k += 1
			if k < len(keys):
				c = max(dist_colors[keys[k]], 0)
			else:
				c = 0
			count = 0
			for k in range(len(dist_colors)):
				if dist_colors[keys[k]] == c or dist_colors[keys[k]] == 0:
					count += 1
				else:
					break
			dist_colors[keys[j]] = curr
			if count == len(dist_colors):
				x = i + 1
				break
	print(x)
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)


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 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)


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 Counter
n = int(input())
u = [int(x) for x in input().split()]
c = Counter()
r = 0
for i in range(n):
	c[u[i]] += 1
	p = list(c.values())
	p.sort(reverse=True)
	if len(p) == 1 or (p[0] == p[-2] and p[-1] == 1) or p[0] - 1 == p[1] == p[-1]:
		r = i
print(r + 1)


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)


import sys
from pprint import pprint
n = int(input())
a = list(map(int, input().split()))
f = [0 for i in range(100005)]
cnt = [0 for i in range(100005)]
mx = 0
ans = 0
for i in range(n):
	x = a[i]
	cnt[f[x]] = max(0, cnt[f[x]] - 1)
	f[x] += 1
	cnt[f[x]] += 1
	mx = max(mx, f[x])
	if mx == 1 or cnt[mx] * mx == i or (cnt[mx - 1] + 1) * (mx - 1) == i:
		ans = i + 1
print(ans)


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 convert(string):
	return string.split(sep=None, maxsplit=-1)

def toint(lst):
	result = []
	for i in lst:
		result.append(int(i))
	return result

def printeach(lst):
	for i in lst:
		print(i, end='')

def valid(dic):
	val = {}
	for i in dic:
		if dic[i] != 0:
			try:
				val[dic[i]] += 1
			except:
				val[dic[i]] = 1
	if len(val) > 2:
		return False
	elif len(val) < 2:
		for i in val:
			if i == 1:
				return True
			elif val[i] == 1:
				return True
			else:
				return False
	else:
		keys = list(val.keys())
		values = list(val.values())
		if keys[0] == 1 and values[0] == 1:
			return True
		elif keys[1] == 1 and values[1] == 1:
			return True
		elif keys[0] - keys[1] == 1 and values[0] == 1:
			return True
		elif keys[0] - keys[1] == -1 and values[1] == 1:
			return True
	return False
n = int(input())
s = toint(convert(input()))
dic = {}
for i in s:
	try:
		dic[i] += 1
	except:
		dic[i] = 1
if valid(dic):
	print(n)
else:
	for i in range(n - 1, -1, -1):
		last = s[i]
		dic[last] -= 1
		if valid(dic):
			print(i)
			break


n = int(input())
u = list(map(int, input().split()))
cnt = [0] * 10
x = 0
for k in range(n):
	i = u[k]
	cnt[i - 1] += 1
	f = 1
	ch = 0
	f1 = 0
	oc = 0
	cnt1 = sorted(cnt)
	for p in range(len(cnt1)):
		j = cnt1[p]
		if not j:
			continue
		if j == 1:
			q = p + 1
			tm = 1
			while 1:
				if q == 10:
					break
				if cnt1[q] == 1:
					q += 1
					continue
				if q == 9 and cnt1[q] == 2:
					q += 1
					continue
				tm = 0
				break
			if tm:
				x = k + 1
				break
			l = list(set(cnt1[p + 1:]))
			if len(l) < 2:
				x = k + 1
				break
			else:
				f = 0
				break
		if not ch:
			ch = 1
			q = p + 1
			if q == 10:
				x = k + 1
				break
			while 1:
				if q == 10:
					f = 0
					break
				if cnt1[q] != cnt1[q - 1]:
					break
				q += 1
			if not f:
				break
			if q == 9 and cnt1[q] == cnt1[p] + 1:
				f = 1
				break
			else:
				f = 0
				break
	if f:
		x = k + 1
print(x)


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))


n = int(input())
a = list(map(int, input().split()))
b = [0 for i in range(10)]
pos = 1
for i in range(n):
	b[a[i] - 1] += 1
	c = []
	for j in range(10):
		if b[j] > 0:
			c.append(b[j])
	c.sort()
	if c[len(c) - 1] == i + 1 or (c[len(c) - 1] == c[len(c) - 2] + 1 and c[len(c) - 2] == c[0]) or (c[len(c) - 1] == c[1] and c[0] == 1):
		pos = i + 1
print(pos)


n = int(input())
a = list(map(int, input().split()))
u = [0] * 10
sl = 0
for i in range(n):
	u[a[i] - 1] += 1
	s = sorted(u)
	for j in range(10):
		if s[j] != 0:
			break
	if s[j] == s[8] and s[9] - s[8] == 1:
		sl = max(sl, i + 1)
	elif s[j] == 1 and s[min(j + 1, 9)] == s[9]:
		sl = max(sl, i + 1)
	elif j == 9:
		sl = max(sl, i + 1)
print(sl)


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())


n = int(input())
a = list(map(int, input().split()))
gg = [0] * 15
ans = 1
for i in range(n):
	gg[a[i]] += 1
	cnt1 = 0
	s = set([])
	for j in gg:
		if not j:
			continue
		if j == 1:
			cnt1 += 1
		else:
			s.add(j)
	mkc = []
	for j in s:
		mkc.append(j)
	if len(s) == 0 or i + 1 in gg:
		ans = max(ans, i + 1)
	if len(s) == 1 and cnt1 == 1:
		ans = max(ans, i + 1)
	if len(s) == 1 and cnt1 == i - 1 and (mkc[0] == 2):
		ans = max(ans, i + 1)
	if len(s) == 2 and cnt1 == 0:
		mkc.sort()
		if mkc[1] == mkc[0] + 1:
			bak = 0
			for j in gg:
				if j == mkc[1]:
					bak += 1
			if bak == 1:
				ans = max(ans, i + 1)
print(ans)


n = int(input())
arr = list(map(int, input().split()))
dp = [0] * 11
ans = 0
for i in range(n):
	dp[arr[i]] += 1
	d = {}
	for j in range(1, 11):
		if dp[j] > 0:
			d[dp[j]] = d.get(dp[j], 0) + 1
	if len(d) == 2:
		s1 = []
		for j in d:
			s1.append(j)
		(a, b) = (s1[0], s1[1])
		if a - 1 == 0 and d[a] == 1:
			ans = max(ans, i + 1)
		if a - 1 > 0 and a - 1 == b and (d[a] == 1):
			ans = max(ans, i + 1)
		if b - 1 == 0 and d[b] == 1:
			ans = max(ans, i + 1)
		if b - 1 > 0 and b - 1 == a and (d[b] == 1):
			ans = max(ans, i + 1)
	if len(d) == 1:
		if dp.count(0) == 10:
			ans = max(ans, i + 1)
		if d.get(1, 0) > 0:
			ans = max(ans, i + 1)
print(ans)


import sys
n = int(sys.stdin.readline().strip())
u = sys.stdin.readline().split()
for i in range(len(u)):
	u[i] = int(u[i])
freq = [0] * 100005
freq_num = [0] * 100005
ans = 1
for i in range(1, len(u) + 1):
	freq[u[i - 1]] += 1
	freq_num[freq[u[i - 1]]] += 1
	if not i == n and freq_num[freq[u[i - 1]]] * freq[u[i - 1]] == i:
		ans = i + 1
	elif freq_num[freq[u[i - 1]]] * freq[u[i - 1]] == i - 1:
		ans = i
print(ans)


maxn = 10 ** 5 + 11
n = int(input())
m = list(map(int, input().split()))
f = [0 for i in range(maxn)]
g = [set() for i in range(maxn)]
ans = 1
known = set()
for j in range(n):
	i = m[j]
	if i not in known:
		known.add(i)
		f[i] = 0
		g[f[i]].add(i)
	g[f[i]].remove(i)
	f[i] += 1
	g[f[i]].add(i)
	if f[i] - 1 > 0 and len(g[f[i] - 1]) * (f[i] - 1) + len(g[f[i]]) == j:
		ans = j + 1
	if j + 1 < n and len(g[f[i]]) * f[i] == j + 1:
		ans = j + 2
	if len(g[f[i]]) == j + 1:
		ans = j + 1
	if len(g[f[i] + 1]) == 1 and len(g[f[i]]) * f[i] + f[i] == j:
		ans = j + 1
	if len(g[f[i]]) * f[i] == j:
		ans = j + 1
print(ans)


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)


n = int(input())
a = [int(x) for x in input().split()]
hsh = [-1 for i in range(10)]
fin = -1
for i in range(n):
	if hsh[a[i] - 1] == -1:
		hsh[a[i] - 1] = i
for i in range(len(hsh)):
	h = [0] * 10
	ans = 0
	if hsh[i] != -1:
		for j in range(n):
			if a[j] - 1 == i and j == hsh[a[j] - 1]:
				pass
			else:
				h[a[j] - 1] += 1
			ln = len(set(h)) - (0 in h)
			if ln == 1:
				ans = j + 1
	fin = max(fin, ans)
print(max(1, fin))


import heapq
MAX = 100000
n = int(input())
a = list(map(int, input().split()))

def ok():
	if len(uniques) == 1:
		return True
	if len(freqs) == 1:
		return maxFreq == 1
	if len(freqs) > 2:
		return False
	return maxFreq - minFreq == 1 and freqs[maxFreq] == 1 or (minFreq == 1 and freqs[minFreq] == 1)
uniques = set()
count = [0] * (MAX + 1)
freqs = {}
maxFreq = 0
h = []
ret = 0
for (i, val) in enumerate(a):
	uniques.add(val)
	count[val] += 1
	curFreq = count[val]
	if curFreq - 1 in freqs:
		freqs[curFreq - 1] -= 1
		if freqs[curFreq - 1] == 0:
			freqs.pop(curFreq - 1)
	freqs.setdefault(curFreq, 0)
	freqs[curFreq] += 1
	maxFreq = max(maxFreq, curFreq)
	heapq.heappush(h, curFreq)
	minFreq = heapq.heappop(h)
	while minFreq not in freqs:
		minFreq = heapq.heappop(h)
	heapq.heappush(h, minFreq)
	if ok():
		ret = i
print(ret + 1)


n = int(input())
u = input().split()
d = {}
for i in set(u):
	d[i] = u.count(i)
for i in range(1, n + 1):
	l = list(set(dict.values(d)))
	if len(l) == 2:
		warn = 0
		warning = 0
		for j in d:
			if d[j] == max(l):
				warning += 1
			elif d[j] == min(l):
				warn += 1
		if warning == 1 and max(l) - min(l) == 1 or (warn == 1 and min(l) == 1):
			res = n - i + 1
			print(res)
			exit(0)
	elif len(l) == 1 and (l[0] == 1 or len(dict.keys(d)) == 1):
		res = n - i + 1
		print(res)
		exit(0)
	d[u[-i]] -= 1
	if d[u[-i]] == 0:
		d.pop(u[-i])


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())
a = []
dctt = {}
maxx = 0
ind = 0
for i in input().split():
	ind += 1
	if i not in dctt:
		dctt[i] = 0
	dctt[i] += 1
	countss = {}
	for (color, count) in dctt.items():
		if count not in countss:
			countss[count] = 0
		countss[count] += 1
	if len(countss) > 2:
		continue
	elif len(countss) == 2:
		a = countss.popitem()
		b = countss.popitem()
		if a[0] == 1 and a[1] == 1:
			maxx = ind
		elif b[0] == 1 and b[1] == 1:
			maxx = ind
		elif abs(a[0] - b[0]) == 1:
			if a[0] > b[0]:
				if a[1] == 1:
					maxx = ind
			elif b[1] == 1:
				maxx = ind
	else:
		a = countss.popitem()
		if a[0] == 1:
			maxx = ind
		elif a[1] == 1:
			maxx = ind
print(maxx)


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)


def equal(a):
	l = len(a)
	for i in range(1, l):
		if a[i - 1] != a[i]:
			return 0
	return 1

def equal1(a):
	b = a[:]
	if b[0] <= b[1]:
		try:
			posi1 = b.index(b[0] + 1)
			b[posi1] = b[0]
			return equal(b)
		except ValueError:
			return 0
	else:
		b[0] = b[0] - 1
		return equal(b)

def equalinlist(a):
	l = len(a)
	if l == 1:
		return 1
	b = a[:]
	try:
		posi = b.index(1)
		if posi > 0:
			b[posi] = b[posi - 1]
		else:
			b[posi] = b[posi + 1]
		if equal(b):
			return 1
		if equal(b) == 0:
			b[posi] = 1
			return equal1(b)
	except ValueError:
		return equal1(b)
n = int(input())
u = list(map(int, input().split()))
a = [1]
b = [u[0]]
x = 1
for i in range(1, n):
	try:
		posi = b.index(u[i])
		a[posi] += 1
	except ValueError:
		b.append(u[i])
		a.append(1)
	if equalinlist(a):
		x = i + 1
print(x)


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 = [0] + list(map(int, input().split()))
cnt = [0] * (10 ** 5 + 10)
freq_dict = Counter({0: n + 1})
ans = 1
for i in range(1, n + 1):
	num = a[i]
	freq_dict[cnt[num]] -= 1
	if freq_dict[cnt[num]] == 0:
		del freq_dict[cnt[num]]
	cnt[num] += 1
	freq_dict[cnt[num]] += 1
	if freq_dict[1] == i:
		ans = i
	elif len(freq_dict) == 2:
		v = [v for (k, v) in freq_dict.items() if k > 0]
		if v[0] == 1:
			ans = i
	elif len(freq_dict) == 3:
		(ks, vs) = ([], [])
		for (k, v) in freq_dict.items():
			if k == 0:
				continue
			ks.append(k)
			vs.append(v)
		if ks[0] > ks[1]:
			(ks[0], ks[1]) = (ks[1], ks[0])
			(vs[0], vs[1]) = (vs[1], vs[0])
		if ks[0] == 1 and vs[0] == 1 or (ks[0] + 1 == ks[1] and vs[1] == 1):
			ans = i
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)


from __future__ import division, print_function
from sys import stdin, stdout
import itertools, os, sys, threading
from collections import deque, Counter, OrderedDict, defaultdict
import heapq
from math import ceil, floor, log, sqrt, factorial, pow, pi, gcd
from fractions import Fraction

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

def si():
	return str(input())

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

def li():
	return list(mi())

def fii():
	return int(stdin.readline())

def fsi():
	return str(stdin.readline())

def fmi():
	return map(int, stdin.readline().split())

def fli():
	return list(fmi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def getKey(item):
	return item[0]

def sort2(l):
	return sorted(l, key=getKey)

def d2(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def ntl(n):
	return [int(i) for i in str(n)]

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

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
graph = defaultdict(list)
visited = [0] * 1000000
col = [-1] * 1000000

def dfs(v, c):
	if visited[v]:
		if col[v] != c:
			print('-1')
			exit()
		return
	col[v] = c
	visited[v] = 1
	for i in graph[v]:
		dfs(i, c ^ 1)

def bfs(d, v):
	q = []
	q.append(v)
	visited[v] = 1
	while len(q) != 0:
		x = q[0]
		q.pop(0)
		for i in d[x]:
			if visited[i] != 1:
				visited[i] = 1
				q.append(i)
		print(x)

def make_graph(e):
	d = {}
	for i in range(e):
		(x, y) = mi()
		if x not in d.keys():
			d[x] = [y]
		else:
			d[x].append(y)
		if y not in d.keys():
			d[y] = [x]
		else:
			d[y].append(x)
	return d

def gr2(n):
	d = {}
	for i in range(n):
		(x, y) = mi()
		if x not in d.keys():
			d[x] = [y]
		else:
			d[x].append(y)
	return d

def connected_components(graph):
	seen = set()

	def dfs(v):
		vs = set([v])
		component = []
		while vs:
			v = vs.pop()
			seen.add(v)
			vs |= set(graph[v]) - seen
			component.append(v)
		return component
	ans = []
	for v in graph:
		if v not in seen:
			d = dfs(v)
			ans.append(d)
	return ans

def primeFactors(n):
	s = set()
	while n % 2 == 0:
		s.add(2)
		n = n // 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			s.add(i)
			n = n // i
	if n > 2:
		s.add(n)
	return s

def find_all(a_str, sub):
	start = 0
	while True:
		start = a_str.find(sub, start)
		if start == -1:
			return
		yield start
		start += len(sub)
n = ii()
l = li()
n += 1
f = [0] * (10 ** 5 + 10)
x = 0
mx = 0
cnt = [0] * (10 ** 5 + 10)
i = 1
ans = 0
for c in l:
	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)


from collections import defaultdict
n = int(input().strip())
nums = [int(i) for i in input().strip().split()]
num_dict = defaultdict(int)
ans = 0
for i in range(n):
	num_dict[nums[i]] += 1
	for key in num_dict:
		num_dict[key] -= 1
		num = num_dict[key]
		current = 0
		for se in num_dict:
			if num == 0 and num_dict[se] != 0:
				num = num_dict[se]
			elif num_dict[se] != 0 and num_dict[se] != num:
				break
		else:
			ans = i
		num_dict[key] += 1
print(ans + 1)


from sys import stdin, stdout, exit
from collections import defaultdict
n = int(input())
a = list(map(int, stdin.readline().split()))
cts = [0] * 11

def valid():
	nonz = [c for c in cts if c != 0]
	nonz.sort()
	if all([nonz[i] == nonz[0] for i in range(len(nonz) - 1)]) and (len(nonz) == 1 or nonz[-1] == nonz[0] + 1):
		return True
	if nonz[0] == 1 and all([nonz[i] == nonz[1] for i in range(1, len(nonz))]):
		return True
	return False
for i in range(n):
	cts[a[i]] += 1
for i in range(n - 1, -1, -1):
	if valid():
		print(i + 1)
		exit()
	cts[a[i]] -= 1


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
			self.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')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
start_time = time.time()

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def get_ints():
	return map(int, sys.stdin.readline().split())
n = int(input())
arr = list(map(int, input().split()))
dp = [0] * 11
ans = 0
for i in range(n):
	dp[arr[i]] += 1
	d = {}
	for j in range(1, 11):
		if dp[j] > 0:
			d[dp[j]] = d.get(dp[j], 0) + 1
	if len(d) == 2:
		s1 = []
		for j in d:
			s1.append(j)
		(a, b) = (s1[0], s1[1])
		if a - 1 == 0 and d[a] == 1:
			ans = max(ans, i + 1)
		if a - 1 > 0 and a - 1 == b and (d[a] == 1):
			ans = max(ans, i + 1)
		if b - 1 == 0 and d[b] == 1:
			ans = max(ans, i + 1)
		if b - 1 > 0 and b - 1 == a and (d[b] == 1):
			ans = max(ans, i + 1)
	if len(d) == 1:
		if dp.count(0) == 10:
			ans = max(ans, i + 1)
		if d.get(1, 0) > 0:
			ans = max(ans, i + 1)
print(ans)


n = int(input())
a = [int(x) for x in input().split()]
d = {}
ans = 0
t = 0
if n == 1:
	print('1')
	exit()
for i in a:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
	x = [d[i] for i in d]
	t += 1
	for i in range(len(x)):
		x[i] -= 1
		tt = list(set(x))
		c = 1
		if 0 in tt:
			c = 2
		if len(tt) == c:
			ans = t
		x[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(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)
		sys.exit()
	if len(D) == 2 and D[1] == 1:
		print(i + 1)
		sys.exit()
	if len(D) == 1 and D[1] > 0:
		print(i + 1)
		sys.exit()
	if len(D) == 1 and list(D.values()) == [1]:
		print(i + 1)
		sys.exit()
	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


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()


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))
n = inp()
a = list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
cnt = [0] * 10
res = 0
for (i, x) in enumerate(a):
	cnt[x] += 1
	tmp = []
	for j in cnt:
		if j:
			tmp.append(j)
	tmp.sort()
	ln = len(tmp)
	if tmp[0] == tmp[-1] == 1 or (tmp[-1] - tmp[0] == 1 and tmp.count(tmp[-1]) == 1 and (tmp.count(tmp[0]) == ln - 1)) or (tmp[0] == 1 and tmp.count(1) == 1 and (tmp.count(tmp[-1]) == ln - 1)) or (ln == 1):
		res = i + 1
print(res)


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().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')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	for _ in range(tc):
		n = ri()
		a = ria()
		d = {}
		md = 0
		ans = 1
		prev = 0
		f = [0] * 100005
		mf = 0
		for i in range(n):
			if a[i] in d:
				d[a[i]] += 1
			else:
				d[a[i]] = 1
			f[d[a[i]]] += 1
			md = max(md, d[a[i]])
			if f[md] == i + 1 or f[md] * md == i or f[md - 1] * (md - 1) == i:
				ans = max(i + 1, ans)
		print(ans)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			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, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			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()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

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

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


def solve(colors):
	n = len(colors)
	color_count = {}
	count_count = {}
	max_x = 1
	for c in colors:
		color_count[c] = 0
	distinct_counts = set()
	for i in range(0, n):
		color = colors[i]
		old_count = color_count[color]
		color_count[color] += 1
		if old_count > 0:
			count_count[old_count] -= 1
			r = count_count[old_count]
			if r == 0 and old_count in distinct_counts:
				distinct_counts.remove(old_count)
		if old_count + 1 in count_count:
			count_count[old_count + 1] += 1
		else:
			count_count[old_count + 1] = 1
		distinct_counts.add(old_count + 1)
		if len(distinct_counts) > 2:
			continue
		interesting_counts = sorted(list(distinct_counts))
		if len(interesting_counts) == 1:
			if interesting_counts[0] == 1 or old_count + 1 == i + 1:
				max_x = i + 1
			continue
		(k1, k2) = interesting_counts
		if k1 + 1 == k2 and count_count[k2] == 1:
			max_x = i + 1
		if k1 == 1 and count_count[k1] == 1 or (k2 == 1 and count_count[k2] == 1):
			max_x = i + 1
	print(max_x)

def main():
	n = int(input().strip())
	colors = list(map(int, input().strip().split()))
	solve(colors)
main()


n = int(input())
arr = list(map(int, input().split()))
lis = [0] * 10
ans = 0
for j in range(n):
	lis[arr[j] - 1] += 1
	num = []
	for i in range(10):
		if lis[i] > 0:
			num.append(lis[i])
	a = max(num)
	if a == 1:
		ans = max(ans, sum(num))
	elif len(num) == 1:
		ans = max(ans, sum(num))
	else:
		b = len(num)
		c = num.count(a)
		d = min(num)
		e = num.count(d)
		if c == 1 and e == b - 1 and (d == a - 1):
			ans = max(ans, sum(num))
		elif c == b - 1 and d == 1:
			ans = max(ans, sum(num))
print(ans)


import sys
input = sys.stdin.buffer.readline

def solution():
	n = int(input())
	l = list(map(int, input().split()))
	color = [0] * 1000000
	f = [0] * 1000000
	m = 0
	ans = 0
	for i in range(n):
		flag = 0
		f[color[l[i]]] -= 1
		color[l[i]] += 1
		f[color[l[i]]] += 1
		m = max(m, color[l[i]])
		if f[1] == i + 1:
			flag = 1
		elif f[i + 1] == 1:
			flag = 1
		elif f[1] == 1 and f[m] * m == i:
			flag = 1
		elif f[m] == 1 and f[m - 1] * (m - 1) == i - m + 1:
			flag = 1
		if flag == 1:
			ans = i + 1
	print(ans)
solution()


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(input())
l = [int(x) for x in input().split()]
d = [0] * 10
ans = 0
for i in range(n):
	ll = {}
	d[l[i] - 1] += 1
	for j in range(10):
		if d[j] != 0:
			if d[j] not in ll:
				ll[d[j]] = 0
			ll[d[j]] += 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)


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
n = int(input())
A = list(map(int, input().split()))
c = Counter()
last_idx = 0
for i in range(len(A)):
	c.update([A[i]])
	u = sum(c.values()) // len(c)
	deducted = False
	match = True
	mc = c.most_common()
	leastcommon = mc[-1][1]
	if len(mc) >= 2:
		if not deducted and mc[0][1] == mc[1][1] + 1:
			del mc[0]
			deducted = True
		elif not deducted and sum(c.values()) == len(c):
			del mc[0]
			deducted = True
	if not deducted and len(mc) > 1 and (leastcommon == 1):
		if sum(c.values()) != len(c):
			del mc[-1]
			deducted = True
	if sum(map(lambda x: x[1], mc)) == mc[0][1] * len(mc):
		match = True
	else:
		match = False
	if len(c) == 1:
		last_idx = i + 1
	elif match and deducted:
		last_idx = i + 1
print(last_idx)


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


def gns():
	return [int(x) for x in input().split()]

def gn():
	return int(input())
n = gn()
ns = gns()
sm = [[0] * 11]
for i in range(n):
	c = ns[i]
	sm.append(list(sm[-1]))
	sm[-1][c] += 1

def check(x):
	x = [i for i in x if i != 0]
	if len(x) == 1:
		return True
	if sum(x) <= len(x) + 1:
		return True
	if 1 in x:
		l1 = x.index(1)
		ot = x[(l1 + 1) % len(x)]
		for i in range(len(x)):
			if i == l1:
				continue
			if x[i] != ot:
				return False
		return True
	m = max(x)
	lm = x.index(m)
	for i in range(len(x)):
		if i == lm:
			continue
		if x[i] != m - 1:
			return False
	return True
i = n
while i >= 0:
	if check(sm[i]):
		print(i)
		quit()
	i -= 1


n = int(input())
a = list(map(int, input().split()))
mem = {}
mark = [0 for _ in range(11)]
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)


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)


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 counts.items())):
			out = i + 1
		elif len(counts) == 1:
			k = next(iter(counts.keys()))
			if k == 1 or len(counts[k]) == 1:
				out = i + 1
	write(out)
main()


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)


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)


n = int(input())
a = [int(x) - 1 for x in input().split()]
counts = [0] * 10
for (ind, i) in enumerate(a):
	counts[i] += 1
	k = sorted([i for i in counts if i])
	if len(k) == 1 or (k[0] == k[-2] and k[-1] - k[-2] == 1) or (k[0] == 1 and k[1] == k[-1]):
		best = ind
print(best + 1)


import sys

class Main:

	def __init__(self):
		self.buff = None
		self.index = 0

	def next(self):
		if self.buff is None or self.index == len(self.buff):
			self.buff = self.next_line()
			self.index = 0
		val = self.buff[self.index]
		self.index += 1
		return val

	def next_line(self):
		return sys.stdin.readline().split()

	def next_ints(self):
		return [int(x) for x in sys.stdin.readline().split()]

	def next_int(self):
		return int(self.next())

	def solve(self):
		n = self.next_int()
		x = self.next_ints()
		cnt = [0 for _ in range(0, max(x) + 1)]
		cc = [0 for _ in range(0, n + 1)]
		mx = 0
		r = 1
		for (i, xx) in enumerate(x):
			cc[cnt[xx]] -= 1
			cnt[xx] += 1
			cc[cnt[xx]] += 1
			mx = max(cnt[xx], mx)
			if cc[mx] * mx == i and cc[1] == 1:
				r = i + 1
			if cc[mx] == 1 and cc[mx - 1] * (mx - 1) + mx - 1 == i:
				r = i + 1
			if mx == 1:
				r = i + 1
		print(r)
Main().solve()


n = int(input())
a = list(map(int, input().split()))
b = [0] * (max(a) + 1)
for i in a:
	b[i] += 1
ans = 1
for i in range(n - 1, -1, -1):
	c = [j for j in b]
	c.sort()
	ind = c.count(0)
	if c.count(c[ind]) == len(c) - ind - 1 and c[-1] - 1 == c[ind] or (c.count(c[-1]) == len(c) - 1 - ind and c[ind] == 1) or (c.count(c[-1]) == len(c) - ind and c[-1] == 1) or (len(c) - ind == 1):
		ans = i + 1
		break
	else:
		b[a[i]] -= 1
print(ans)


n = int(input())
u = [int(i) for i in input().split()]
cnt = [0 for i in range(10)]
ans = 0
for i in range(n):
	cnt[u[i] - 1] += 1
	cm = max(cnt)
	c0 = cnt.count(0)
	gen = cm - 1
	if cnt.count(gen) == 10 - c0 - 1:
		ans = i + 1
	else:
		temp = []
		for x in cnt:
			if x != 0:
				temp.append(x)
		if len(set(temp)) == 2 and temp.count(1) == 1:
			ans = i + 1
		elif len(set(temp)) == 1 and temp.count(1) > 0:
			ans = i + 1
print(ans)


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()))
dic = {a[0]: 1}
su = 1
kq = 1
for i in range(1, n):
	if dic.get(a[i], 0) == 0:
		dic.update({a[i]: 1})
	else:
		dic[a[i]] += 1
	su += 1
	cach = len(list(dic.keys()))
	c = 0
	c_ = 0
	for z in list(dic.keys()):
		if cach == 1:
			continue
		if cach == su:
			kq = su
			continue
		if dic[z] == (su - 1) / (cach - 1):
			c += 1
		if dic[z] == (su - 1) / cach:
			c_ += 1
	if c == cach - 1 or c_ == cach - 1:
		kq = su
print(kq)


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)


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 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 d.keys():
		d[occ[numbers[k]]] += 1
	else:
		d[occ[numbers[k]]] = 1
	if len(d.keys()) == 2 and 1 in d.keys() and (2 in d.keys()):
		if d[2] == 1:
			places.append(k)
		if d[1] == 1:
			places.append(k)
	elif len(d.keys()) == 2 and 1 in d.keys():
		if d[1] == 1:
			places.append(k)
	elif len(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(d.keys()) == 1:
		jo = 1
		for i in d.keys():
			if d[i] == 1:
				places.append(k)
				jo = 0
		if jo:
			if 1 in d.keys():
				places.append(k)
if len(places) > 0:
	print(places[-1] + 1)
else:
	print(0)


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)


n = int(input())
u = [int(s) for s in input().split()]
a = [0 for i in range(10)]
im = 0
for i in range(n):
	a[u[i] - 1] += 1
	d = dict()
	for j in a:
		if j != 0:
			d[j] = d.setdefault(j, 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())
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)


n = int(input())
s = list(map(int, input().split()))[::-1]
from collections import Counter
c = Counter(s)

def r(c):
	l = [c[i] for i in c if c[i]]
	l.sort()
	if len(l) <= 1:
		return 1
	if l[-1] > l[-2]:
		return l[:-1] == [l[0]] * (len(l) - 1) and l[-1] - l[-2] == 1
	elif l == [1] * len(l):
		return 1
	else:
		return l.count(1) == 1 and l[1:] == [l[-1]] * (len(l) - 1)
cnt = 0
for i in s:
	if r(c):
		print(n - cnt)
		exit()
	c[i] -= 1
	cnt += 1


import math
from decimal import Decimal

def na():
	n = int(input())
	b = [int(x) for x in input().split()]
	return (n, b)

def nab():
	n = int(input())
	b = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	return (n, b, c)

def dv():
	(n, m) = map(int, input().split())
	return (n, m)

def dva():
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	return (n, m, b)

def eratosthenes(n):
	sieve = list(range(n + 1))
	for i in sieve:
		if i > 1:
			for j in range(i + i, len(sieve), i):
				sieve[j] = 0
	return sorted(set(sieve))

def nm():
	n = int(input())
	b = [int(x) for x in input().split()]
	m = int(input())
	c = [int(x) for x in input().split()]
	return (n, b, m, c)

def dvs():
	n = int(input())
	m = int(input())
	return (n, m)

def ist(x):
	d = 1
	while d < x:
		d *= 2
	return d == x
(n, a) = na()
mx = 100000
dop = [0] * mx
dop[a[0] - 1] = 1
ans = 1
kz = 1
kznd = 1
dopdop = 0
dopnd = 1
dopndcz = mx - 1
for i in range(1, n):
	cc = a[i] - 1
	dop[cc] += 1
	if dop[cc] == 1:
		dopndcz -= 1
		dopnd += 1
	if dop[cc] == 2:
		dopnd -= 1
	if dop[cc] == kz:
		kznd += 1
		dopdop = max(0, dopdop - 1)
	if dop[cc] == kz - 1:
		dopdop += 1
	if dop[cc] > kz:
		dopdop = kznd - 1
		kz = dop[cc]
		kznd = 1
	if kznd == 1 and dopdop == mx - 1 - dopndcz or (dopnd == 1 and kznd == mx - 1 - dopndcz) or dopnd == mx - dopndcz:
		ans = i + 1
print(ans)


n = int(input())
l = list(map(int, input().split()))
c = [0] * 10
ans = 1
c[l[0] - 1] += 1
for i in range(1, n):
	if i != 0:
		max = -10
		min = 10 ** 18
		for j in range(10):
			if c[j] != 0:
				if c[j] > max:
					max = c[j]
				if c[j] < min:
					min = c[j]
		boo = 0
		ba = 0
		flag = 0
		for j in c:
			if j == min:
				boo += 1
			if j == max:
				ba += 1
			if min < j < max:
				flag = 1
				break
		if boo == 1 and min == 1 or (ba == 1 and max - min == 1):
			if flag == 0:
				ans = i
		if abs(max - min) == 0:
			ans = i + 1
	c[l[i] - 1] += 1
print(ans)


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 = 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
for i in range(n):
	d[a[i]] += 1
	l = list(d.values())
	l = list(set(l))
	ll = list(d.values())
	l.sort()
	if l[0] == 0:
		l.pop(l[0])
	if len(l) == 2:
		if abs(l[0] - l[1]) == 1 and ll.count(l[1]) == 1:
			x = max(x, i + 1)
		elif l[0] == 1 and ll.count(1) == 1:
			x = max(x, i + 1)
	if len(l) == 1 and l[0] == 1:
		x = max(x, i + 1)
print(x)


import collections
import collections
n = int(input())
u = list(map(int, input().split()))
(g, cnt) = ([0] * 10, 0)
ans = 0
for i in range(n):
	g[u[i] - 1] += 1
	unique = set(g)
	unique.discard(0)
	if len(unique) == 1:
		k = unique.pop()
		if k == 1:
			ans = i
		elif g.count(k) == 1:
			ans = i
	elif len(unique) == 2:
		if 1 in unique and g.count(1) == 1:
			ans = i
		else:
			(a, b) = unique
			if a < b:
				(b, a) = (a, b)
			if a - b == 1 and g.count(a) == 1:
				ans = i
print(ans + 1)


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)