"Humankind cannot gain anything without first giving something in return. To obtain, something of equal value must be lost. That is alchemy's first law of Equivalent Exchange. In those days, we really believed that to be the world's one, and only truth."
-- Alphonse Elric
Now, here we have an equivalent exchange law for triangles which states that two right-angled isosceles triangles of the same color can be made into a square of the same color using Alchemy.
You are given N$N$ right-angled isosceles colored triangles numbered from 1$1$ to N$N$. For each triangle, the two equal sides have a length of 1$1$ unit. The Color of i$i$-th triangle is given by Ci$C_i$.
To create a tower, we choose some consecutive (2×k)+1$2 \times k)+1$ triangles for any k≥0$k \geq 0$. We then pick some 2×k$2 \times k$ of them (these need not be consecutive), and form k$k$ pairs of triangles such that both triangles in pair have the same color. Also, each of the 2×k$2 \times k$ should be in exactly one pair. Then the two triangles in each pair are joined using Alchemy (following the law of equivalent exchange for triangles) to form squares and these k$k$ squares are placed one upon other. The one remaining triangle is placed as a roof to the tower. This results in a tower of the height of k$k$.
Find the maximum height of the tower that can be formed. 
In other words, you should select the largest consecutive segment of triangles, such that you can form a tower using every single one of those triangles. In particular, you leave out one triangle, which will form the roof, and the other triangles should all be paired up such that both triangles in a pair have the same colour.

-----Input:-----
- The first line contains T$T$, the number of test cases. Then the test cases follow. 
- For every test case, the first line contains N$N$ denoting the number of triangles.
- For every test case, the second line contains N$N$ space-separated integers Ci$C_{i}$ denoting the color of the triangles. ( 1≤i≤N$1 \leq i \leq N$).

-----Output:-----
For every test case, output a single integer denoting the maximum height of the tower that can be formed.

-----Constraints-----
- 1≤T≤100$1 \leq T \leq 100$ 
- 1≤N≤105$1 \leq N \leq 10^{5}$ 
- 1≤Ci≤30$1 \leq C_{i} \leq 30$ 
- Sum of N$N$ over all test cases doesn't exceed 5×105$5\times 10^{5}$ 

-----Sample Input:-----
4
14
5 4 2 2 3 2 1 3 2 7 4 9 9 9
3
1 2 1
3
1 1 1
5
1 2 3 4 1

-----Sample Output:-----
3
1
1
0

-----EXPLANATION:-----
- #1$1$: The subarray [2,2,3,2,1,3,2]$[2, 2, 3, 2, 1, 3, 2]$ results in a tower of height 3$3$.
- #2$2$: The subarray [1,2,1]$[ 1, 2, 1 ]$ results in a tower of height 1$1$.
- #3$3$: The subarray [1,1,1]$[ 1, 1, 1 ]$ results in a tower of height 1$1$. 
- #4$4$: The subarrays [1]$[ 1 ]$, [2]$[ 2 ]$ , [3]$[ 3 ]$, [4]$[ 4 ]$ and [1]$[ 1 ]$ all results in a tower of height 0$0$.

The above tower is possible by subarray [2,2,3,2,1,3,2]$[2, 2, 3, 2, 1, 3, 2]$ resulting in a height of 3$3$ in test case 1$1$.

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Mathematics


Solutions:
for t in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	dictionary = {0: 0}
	parity = 0
	k = 0
	for i in range(n):
		parity ^= 1 << c[i] - 1
		if parity not in dictionary:
			dictionary[parity] = i + 1
		for j in range(30):
			x = parity ^ 1 << j
			if x in dictionary:
				k = max(k, i - dictionary[x])
	print(k // 2)


for _ in range(int(input())):
	input()
	cs = [int(x) - 1 for x in input().split()]
	first = {0: 0}
	last = {}
	v = 0
	for (i, c) in enumerate(cs):
		v ^= 1 << c
		if v not in first:
			first[v] = i + 1
		last[v] = i + 1
	ans = max((last.get(v ^ 1 << c, 0) - i for c in range(max(cs) + 1) for (v, i) in first.items()))
	assert ans % 2 == 1
	print(ans // 2)


import numpy as np
tests = int(input())
for _ in range(tests):
	n = int(input())
	nums = [int(j) - 1 for j in input().split()]
	pow_2 = [1 for _ in range(30)]
	for i in range(1, 30):
		pow_2[i] = 2 * pow_2[i - 1]
	colors = [-1 for _ in range(30)]
	seen = dict()
	seen[0] = -1
	max_height = 0
	num = 0
	for i in range(n):
		colors[nums[i]] = -colors[nums[i]]
		num += pow_2[nums[i]] * colors[nums[i]]
		for j in range(30):
			new_num = num + pow_2[j] * -colors[j]
			if new_num in seen:
				max_height = max(max_height, (i - seen[new_num]) // 2)
		if num not in seen:
			seen[num] = i
	print(max_height)


from sys import stdin, stdout
for tc_ in range(int(stdin.readline())):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	dic = {0: -1}
	ans = last = 0
	for i in range(n):
		last ^= 1 << a[i] - 1
		for j in range(30):
			x = last ^ 1 << j
			if x in dic:
				ans = max(ans, i - dic[x])
		if last not in dic:
			dic[last] = i
	stdout.write(f'{ans >> 1}\n')


for t in range(int(input())):
	n = int(input())
	l = [int(j) - 1 for j in input().split()]
	d = dict()
	st = 0
	d[st] = -1
	ans = 1
	for i in range(n):
		st = st ^ 1 << l[i]
		for j in range(30):
			st1 = st
			st1 = st1 ^ 1 << j
			if st1 in d and d[st1] != i - 1:
				ans = max(ans, i - d[st1])
		if st not in d:
			d[st] = i
	print(ans // 2)


for i in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	d = {}
	d[0] = -1
	parity = 0
	ans = 0
	for i in range(n):
		parity ^= 1 << c[i] - 1
		for t in range(30):
			x = parity ^ 1 << t
			if x in d.keys():
				ans = max(ans, i - d[x])
		if parity not in d.keys():
			d[parity] = i
	print(ans // 2)


def answers():
	(answ, x) = (0, 0)
	e = dict()
	e[x] = -1
	for i in range(n):
		x ^= 1 << a[i] - 1
		if x not in e.keys():
			e[x] = i
		for j in range(30):
			answ = max(answ, i - e.get(x ^ 1 << j, i))
	return answ // 2
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(answers())


def answer():
	(ans, x) = (0, 0)
	d = dict()
	d[x] = -1
	for i in range(n):
		x ^= 1 << a[i] - 1
		if x not in d.keys():
			d[x] = i
		for j in range(30):
			ans = max(ans, i - d.get(x ^ 1 << j, i))
	return ans // 2
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(answer())