Pushpa has entered Chefland and wants to establish Pushpa-Raj here too. 

Chefland has N towers where the height of the i^{th} tower is H_{i}. To establish Pushpa-Raj, Pushpa does the following:
Initially, Pushpa chooses any tower i (1≤ i ≤ N) and lands on the roof of that tower.
Let X denote the height of the tower Pushpa is currently on, then, Pushpa can land on the roof of any tower j (1≤ j ≤ N) such that the height of the j^{th} tower is (X+1). 

Let i denote the index of the tower on which Pushpa lands, then, the height of all towers except tower i increases by 1 after each jump including the initial jump.

To establish Pushpa-Raj, Pushpa wants to land at the maximum height possible. Determine the maximum height Pushpa can reach.

------ Input Format ------ 

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N - the number of towers
- The second line of each test case contains N space-separated integers H_{1}, H_{2}, \dots, H_{N} denoting the initial heights of each of the towers from the ground.

------ Output Format ------ 

For each test case, output in a single line the maximum height achieved by Pushpa.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ H_{i} ≤ 10^{9}$

----- Sample Input 1 ------ 
2
4
1 2 1 3
1
2
----- Sample Output 1 ------ 
3
2
----- explanation 1 ------ 
- Test case $1$: If Pushpa chooses to start from tower at index $1$ with height of $1$ unit, then, the new heights will be $[ 1, 3, 2, 4 ]$. He can then jump to the $3^{rd}$ tower (with height $2$ units). The updated heights of the towers is $[2, 4, 2, 5]$. Pushpa is unable to make any more jumps. 

The optimal way to in this case is to take an initial jump at tower $4$ with height $3$. The maximum height Pushpa can reach is $3$.

- Test case $2$: There is only $1$ tower so Pushpa reaches the maximum height of $2$ units.

Source: codechef | Difficulty: EASY
Tags: Sorting

Amortized analysis


Solutions:
def maxHeight(List):
	return max(set(List), key=List.count)
t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	x = maxHeight(a) + a.count(maxHeight(a)) - 1
	y = max(a) + a.count(max(a)) - 1
	print(x if x > y else y)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	for j in set(l):
		l1.append(j + l.count(j) - 1)
	print(max(l1))


for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))[:n]
	s = list(set(h))
	(l, l1) = ([], [])
	for i in range(len(s)):
		l.append(h.count(s[i]))
		l1.append(s[i] + l[i] - 1)
	print(max(l1))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	for j in set(a):
		b.append(j + a.count(j) - 1)
	print(max(b))


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	cnt = 0
	s = 0
	if len(l) == 1:
		print(l[0])
	else:
		for i in range(n - 1, -1, -1):
			if l[i - 1] == l[i]:
				cnt += 1
			else:
				if s < l[i] + cnt:
					s = l[i] + cnt
				cnt = 0
		print(s)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = []
	for i in set(l):
		a.append(i + l.count(i) - 1)
	print(max(a))


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	h = Counter(map(int, input().split()))
	max_value = 0
	for key in h:
		max_value = max(max_value, key + h[key] - 1)
	print(max_value)


for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	c = []
	if n == 1:
		print(h[0])
	else:
		h1 = list(set(h))
		for i in h1:
			d = h.count(i)
			c = c + [i + d - 1]
		print(max(c))


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = {}
	for i in a:
		b[i] = b.get(i, 0) + 1
	max_jump = 0
	for (x, y) in b.items():
		max_jump = max([max_jump, x + y - 1])
	print(max_jump)


t = int(input())
while t > 0:
	n = int(input())
	h = list(map(int, input().split()))
	height = []
	for i in set(h):
		height.append(i + h.count(i) - 1)
	print(max(height))
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	n_list = list(map(int, input().split()))
	x = max(set(n_list), key=n_list.count) + n_list.count(max(set(n_list), key=n_list.count)) - 1
	y = max(n_list) + n_list.count(max(n_list)) - 1
	print(x if x > y else y)


for i in range(int(input())):
	n = int(input())
	h = [int(num) for num in input().split()]
	ct = []
	if n == 1:
		print(h[0])
	else:
		d = list(set(h))
		for i in d:
			c = h.count(i)
			ct = ct + [i + c - 1]
		print(max(ct))


for i in range(int(input())):
	n = int(input())
	h = [int(num) for num in input().split()]
	c = list(set(h))
	(a, b) = ([], [])
	for j in range(len(c)):
		a.append(h.count(c[j]))
		b.append(c[j] + a[j] - 1)
	print(max(b))


try:
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		d = {}
		for h in arr:
			if h in d:
				d[h] += 1
			else:
				d[h] = 1
		amax = max(arr)
		for h in d.keys():
			if h + d[h] - 1 > amax:
				amax = h + d[h] - 1
		print(amax)
except Exception:
	pass


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	mp = {}
	for i in range(n):
		if l[i] not in mp:
			mp[l[i]] = 1
		else:
			mp[l[i]] += 1
	max_ht = -float('inf')
	for i in mp:
		max_ht = max(i + (mp[i] - 1), max_ht)
	print(max_ht)


t = int(input())
lists = []
for i in range(t):
	n = int(input())
	l = input().split(' ')
	for i in range(len(l)):
		l[i] = int(l[i])
	d = {}
	if n == 1:
		lists.append(l[0])
	else:
		for i in range(len(l)):
			d[l[i]] = 0
		for i in range(len(l)):
			d[l[i]] += 1
		y2 = sorted(d.items(), key=lambda kv: (kv[1], kv[0]))
		ans = 0
		for i in range(len(y2)):
			a1 = y2[i][0]
			a2 = y2[i][1]
			bb = a1 + a2 - 1
			if ans < bb:
				ans = bb
		lists.append(ans)
for i in range(len(lists)):
	print(lists[i])


t = int(input())
for i in range(t):
	n = int(input())
	L = sorted(list(map(int, input().strip().split())))
	D = {}
	F = []
	for item in L:
		if item in D.keys():
			continue
		D[item] = L.count(item)
		F.append(int(item) + int(D[item] - 1))
	print(max(F))


t = int(input())
for t in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	d = {}
	for a in arr:
		if a in d:
			d[a] += 1
		else:
			d[a] = 1
	max_h = 0
	for key in d:
		max_h = max(max_h, key + d[key] - 1)
	print(max_h)


for t in range(int(input())):
	input()
	hj = [int(i) for i in input().split()]
	ploy = 0
	for i in set(hj):
		if ploy < i + hj.count(i) - 1:
			ploy = i + hj.count(i) - 1
	print(ploy)


def pushpaRaj(towerHeights):
	counts = {}
	maxCount = 0
	for i in range(len(towerHeights)):
		if counts.get(towerHeights[i]) == None:
			counts[towerHeights[i]] = 1
		else:
			counts[towerHeights[i]] += 1
		if towerHeights[i] + counts[towerHeights[i]] - 1 > maxCount:
			maxCount = towerHeights[i] + counts[towerHeights[i]] - 1
	return max(maxCount, max(counts))
nTests = int(input())
for i in range(nTests):
	nTowers = int(input())
	towerHeights = list(map(int, input().split(' ')))
	print(pushpaRaj(towerHeights))


n = int(input())
for i in range(n):
	k = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	x = 0
	for i in s:
		x = max(x, a.count(i) + i - 1)
	print(x)


t = int(input())
for ni in range(t):
	n = int(input())
	h = [int(i) for i in input().split()]
	s = set(h)
	m = 0
	for i in s:
		m = max(m, h.count(i) + i - 1)
	print(m)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	key = set(arr)
	ans = 0
	for i in key:
		ans = max(ans, arr.count(i) + i - 1)
	print(ans)


for i in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	H = set(h)
	b = 0
	for i in H:
		v = h.count(i) + i - 1
		if v > b:
			b = v
	print(b)


testcases = int(input())
for i in range(testcases):
	n = int(input())
	data = list(map(int, input().split()))
	if len(data) == 1:
		print(max(data))
	else:
		c = 0
		m = 0
		data.sort()
		for i in range(n - 1, 0, -1):
			if data[i] == data[i - 1]:
				c = c + 1
			elif m < data[i] + c:
				m = data[i] + c
				c = 0
		print(m)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	if len(l) == 1:
		print(l[0])
	else:
		m = 0
		c = 0
		for i in range(n - 1, 0, -1):
			if l[i] == l[i - 1]:
				c += 1
			elif m < l[i] + c:
				m = l[i] + c
				c = 0
		print(m)


for i in range(int(input())):
	k = int(input())
	a = list(map(int, input().split()))
	a = sorted(a)
	if len(a) == 1:
		print(a[0])
	else:
		m = 0
		c = 0
		for i in range(k - 1, 0, -1):
			if a[i] == a[i - 1]:
				c += 1
			elif m < a[i] + c:
				m = a[i] + c
				c = 0
		print(m)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	new = set(arr)
	maxx = 0
	for i in new:
		temp = arr.count(i) + i - 1
		maxx = max(temp, maxx)
	print(maxx)


n = int(input())
for _ in range(n):
	k = int(input())
	l = list(map(int, input().split()))
	maxi = 0
	for i in set(l):
		new = l.count(i)
		cou = new + i - 1
		if cou > maxi:
			maxi = cou
	print(maxi)


T = int(input())
for i in range(T):
	N = int(input())
	l = list(map(int, input().split()))
	d = {}
	c = 0
	for j in l:
		if j in d:
			d[j] += 1
		else:
			d[j] = 1
	for k in d:
		c = max(c, k + d[k] - 1)
	print(c)


for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	temp = []
	for i in set(h):
		temp.append(i + h.count(i) - 1)
	temp.append(max(h))
	print(max(temp))


for j in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	count = 0
	maxi = max(l)
	for k in range(n - 1):
		if l[k] == l[k + 1]:
			count = count + 1
		else:
			if count + l[k] > maxi:
				maxi = count + l[k]
			count = 0
	if l[n - 1] == l[n - 2]:
		count = l.count(l[n - 1])
		if maxi < l[n - 1] + count - 1:
			maxi = l[n - 1] + count - 1
	print(maxi)


from collections import Counter
for tc in range(int(input())):
	n = int(input())
	k = list(map(int, input().split()))
	c = Counter(k)
	z = [k + v - 1 for (k, v) in c.items()]
	print(max(max(z), max(k)))


for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	h_set = list(set(h))
	best = 0
	for v in h_set:
		c = h.count(v)
		height = v + c - 1
		if height > best:
			best = height
	print(best)


from collections import Counter
testcase = int(input())
for i in range(testcase):
	n = int(input())
	lst = list(map(int, input().split()))
	cnt = Counter(lst)
	best = [j + k - 1 for (j, k) in cnt.items()]
	print(max(best))


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	a = list(map(int, input().split(' ')))
	d = dict()
	for i in range(0, len(a)):
		if a[i] not in d:
			d[a[i]] = 1
		else:
			d[a[i]] += 1
	x = []
	for (i, j) in d.items():
		x.append(i + j)
	print(max(max(x) - 1, max(a)))


def mostFrequent(arr, n):
	max_count = 1
	res = arr[0]
	curr_count = 1
	for i in range(1, n):
		if arr[i] == arr[i - 1]:
			curr_count += 1
		else:
			curr_count = 1
		if curr_count > max_count:
			max_count = curr_count
			res = arr[i - 1]
	return res
for test in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(l[0])
	else:
		l.sort(reverse=True)
		mx = mostFrequent(l, n)
		if mx + l.count(mx) - 1 > max(l):
			print(mx + l.count(mx) - 1)
		else:
			print(max(l) + l.count(max(l)) - 1)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	c = Counter(h)
	best = [k + v - 1 for (k, v) in c.items()]
	print(max(max(best), max(h)))


t = int(input())
for _ in range(t):
	n = int(input())
	h = list(map(int, input().split()))
	a = list(set(h))
	pushpa = []
	for i in range(len(a)):
		count = a[i] + h.count(a[i]) - 1
		pushpa.append(count)
	print(max(pushpa))


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	res = max(lst)
	d = {i: lst.count(i) for i in set(lst)}
	for i in d:
		res = max(d[i] + i - 1, res)
	print(res)


for _ in range(int(input())):
	p = []
	N = int(input())
	l = list(map(int, input().split()))
	for i in set(l):
		p = p + [i + l.count(i) - 1]
	print(max(p))


t = int(input())
for _ in range(t):
	N = int(input())
	heights = list(map(int, input().split()))
	sorted_heights = sorted(heights)
	my_dict = {}
	for height in sorted_heights:
		if height in my_dict:
			my_dict[height] += 1
		else:
			my_dict[height] = height
	print(max(my_dict.values()))


for _ in range(int(input())):
	n = int(input())
	s = sorted(list(map(int, input().split())))
	c = 1
	num = 0
	maxnum = 0
	if n == 1:
		print(s[0])
	else:
		for i in range(n - 1):
			if s[i] == s[i + 1]:
				c += 1
			else:
				num = s[i] + c - 1
				maxnum = max(num, maxnum)
				c = 1
		num = s[n - 1] + c - 1
		maxnum = max(num, maxnum)
		print(maxnum)


from collections import Counter
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr1 = Counter(arr)
	ans = 0
	for i in arr1:
		ans = max(ans, i + arr1[i] - 1)
	print(ans)


for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	h = {}
	for j in l:
		if j in h:
			h[j] = h[j] + 1
		else:
			h[j] = 1
	ans = 0
	for j in l:
		ans = max(ans, h[j] + j - 1)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		if i in d:
			d[i] = d[i] + 1
		else:
			d[i] = 1
	ans = 0
	for j in l:
		ans = max(ans, j + d[j] - 1)
	print(ans)