Given elements of a stack, clone the stack without using extra space.
Example 1:
Input:
N = 10
st[] = {1, 1, 2, 2, 3, 4, 5, 5, 6, 7}
Output:
1 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function clonestack() which takes the input stack st[], an empty stack cloned[], you have to clone the stack st into stack cloned.
The driver code itself prints 1 in the output if the stack st is cloned properly and prints 0 otherwise.
Expected Time Complexity: O(N*N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 1000
1<= st[i] <= 10^{5}

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N*N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def clonestack(self, st, cloned):

        # code here 

Solutions:
class Solution:

	def clonestack(self, st, cloned):
		l = []
		while st:
			l.append(st.pop())
		while l:
			cloned.append(l.pop())


class Solution:

	def clonestack(self, st, cloned):
		for i in st:
			cloned.append(i)


class Solution:

	def clonestack(self, st, cloned):
		count = 0
		n = len(st)
		while count < n:
			k = st.pop()
			while len(st) != count:
				cloned.append(st.pop())
			st.append(k)
			while len(cloned):
				st.append(cloned.pop())
			count += 1
		while len(st):
			cloned.append(st.pop())


class Solution:

	def clonestack(self, st, cloned):
		k = len(st)
		while k > 0:
			n = k
			n2 = k - 1
			while n - 1 > 0:
				popped = st.pop()
				cloned.append(popped)
				n -= 1
			temp = st.pop()
			st.append(temp)
			while n2 > 0:
				popped = cloned.pop()
				st.append(popped)
				n2 -= 1
			cloned.append(temp)
			k -= 1
		return cloned


import sys
sys.setrecursionlimit(100000)

class Solution:

	def clonestack(self, st, cloned):
		if len(st) == 0:
			return
		val = st.pop()
		self.clonestack(st, cloned)
		cloned.append(val)


class Solution:

	def clonestack(self, st, cloned):
		cloned.extend(st)


class Solution:

	def clonestack(self, st, cloned):
		sst = []
		while st:
			sst.append(st.pop())
		while sst:
			cloned.append(sst.pop())
		return cloned


class Solution:

	def clonestack(self, st, cloned):
		while st:
			n = st.popleft()
			cloned.append(n)


class Solution:

	def clonestack(self, st, cloned):
		while st:
			q = st.pop()
			cloned.appendleft(q)


class Solution:

	def clonestack(self, st, cloned):
		length = len(st)
		for i in range(length):
			while len(st):
				cloned.append(st.pop())
			temp = cloned.pop()
			for j in range(length - i - 1):
				st.append(cloned.pop())
			cloned.append(temp)


import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def clone(self, stack, cloned):
		if len(stack):
			a = stack.pop()
			self.clone(stack, cloned)
			cloned.append(a)

	def clonestack(self, st, cloned):
		self.clone(st, cloned)


class Solution:

	def clonestack(self, st, cloned):
		while len(st) != 0:
			cloned.append(st.popleft())


class Solution:

	def clonestack(self, st, cloned):
		temp = []
		for i in range(len(st)):
			temp.append(st.pop())
		for i in range(len(temp)):
			cloned.append(temp.pop())
		return cloned


class Solution:

	def clonestack(self, st, cloned):
		n = len(st)
		n -= 1
		base = 0
		while n > 0:
			temp = st.pop()
			while len(st) > base:
				temp2 = st.pop()
				cloned.append(temp2)
			st.append(temp)
			while len(cloned) > 0:
				temp3 = cloned.pop()
				st.append(temp3)
			base += 1
			n -= 1
		while len(st) > 0:
			temp4 = st.pop()
			cloned.append(temp4)


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def clonestack(self, st, cloned, idx=0):
		if idx == len(st):
			return cloned
		cloned.append(st[idx])
		self.clonestack(st, cloned, idx + 1)


class Solution:

	def clonestack(self, st, cloned):
		x = []
		for i in range(len(st)):
			x.append(st.pop())
		for i in range(len(x)):
			cloned.append(x.pop())


class Solution:

	def clonestack(self, st, cloned):
		while st:
			cloned.insert(0, st.pop())


class Solution:

	def clonestack(self, st, cloned):
		for ele in st:
			cloned.append(ele)
		return cloned


class Solution:

	def clonestack(self, st, cloned):
		n = len(st)
		for i in range(n):
			while len(st) > 1:
				cloned.append(st.pop())
			e = st.pop()
			for _ in range(n - i - 1):
				st.append(cloned.pop())
			cloned.append(e)
		return cloned


class Solution:

	def clonestack(self, st, cloned):
		for item in st:
			cloned.append(item)


class Solution:

	def clonestack(self, st, cloned):
		temp = st
		while len(temp) != 0:
			cloned.insert(0, temp.pop())


class Solution:

	def clonestack(self, st, cloned):
		for x in st:
			cloned.append(x)


class Solution:

	def clonestack(self, st, cloned):
		while len(st):
			cloned.appendleft(st.pop())


class Solution:

	def clonestack(self, st, cloned):
		for i in range(len(st)):
			cloned.append(st.popleft())


class Solution:

	def clonestack(self, st, cloned):
		length = len(st)
		for i in range(length - 1):
			val = st.pop()
			for _ in range(len(st) - i):
				cloned.append(st.pop())
			st.append(val)
			while cloned:
				st.append(cloned.pop())
		while st:
			cloned.append(st.pop())


class Solution:

	def clonestack(self, st, cloned):
		count = 0
		while count != len(st) - 1:
			top = st.pop()
			while count != len(st):
				cloned.append(st.pop())
			st.append(top)
			while len(cloned):
				st.append(cloned.pop())
			count += 1
		while len(st):
			cloned.append(st.pop())


class Solution:

	def clonestack(self, st, cloned):
		for i in range(len(st) - 1, -1, -1):
			ele = st[-1]
			st.pop()
			cloned.append(ele)
		cloned.reverse()
		return cloned


class Solution:

	def clonestack(self, st, cloned):
		n = len(st)
		for i in range(n, 0, -1):
			for _ in range(i):
				cloned.append(st.pop())
			k = cloned[-1]
			for _ in range(i):
				st.append(cloned.pop())
			cloned.append(k)
		return cloned


class Solution:

	def clonestack(self, st, cloned):
		n = 0
		for i in range(len(st)):
			cloned.append(st[i])
		return cloned


class Solution:

	def clonestack(self, st, cloned):
		if len(st) == 0:
			return
		while st:
			cloned.append(st.pop())
		if len(cloned) == 1:
			return
		for i in range(len(cloned)):
			x = cloned.pop()
			while len(cloned) != i:
				st.append(cloned.pop())
			cloned.append(x)
			while st:
				cloned.append(st.pop())


class Solution:

	def clonestack(self, st, cloned):
		while st:
			tmp = st.pop()
			cloned.append(tmp)
			cloned.rotate(1)
		return 1


class Solution:

	def clonestack(self, st, cloned):
		i = 0
		while i < len(st) // 2:
			(st[i], st[len(st) - i - 1]) = (st[len(st) - i - 1], st[i])
			i += 1
		while len(st) > 0:
			cloned.append(st.pop())
		return cloned


class Solution:

	def clonestack(self, st, cloned):
		for i in reversed(range(1, len(st))):
			item = st.pop()
			for j in range(i):
				cloned.append(st.pop())
			st.append(item)
			while cloned:
				st.append(cloned.pop())
		while st:
			cloned.append(st.pop())


import sys
sys.setrecursionlimit(150000000)

class Solution:

	def clonestack(self, st, cloned):

		def push(val, cloned):
			if len(cloned) == 0:
				cloned.append(val)
				return
			x = cloned.pop()
			push(val, cloned)
			cloned.append(x)
		i = len(st) - 1
		while i >= 0:
			push(st[i], cloned)
			i -= 1


class Solution:

	def clonestack(self, st, cloned):
		for elements in st:
			cloned.append(elements)
		return cloned


from numpy import *

class Solution:

	def clonestack(self, st, cloned):
		for i in range(len(st)):
			cloned.append(st[i])


class Solution:

	def clonestack(self, st, cloned):
		for j in st:
			cloned.append(j)


class Solution:

	def clonestack(self, st, cloned):
		for i in range(len(st)):
			cloned.insert(0, st.pop())
		return cloned


class Solution:

	def clonestack(self, st, cloned):
		if len(st) != 0:
			for val in st:
				cloned.append(val)
			return 1
		else:
			return 0
from collections import deque
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = list(map(int, input().split()))
		st = deque()
		copy = []
		for i in range(N):
			st.append(arr[i])
			copy.append(arr[i])
		copy = copy[::-1]
		cloned = deque()
		ob = Solution()
		ob.clonestack(st, cloned)
		check = []
		while len(cloned):
			check.append(cloned.pop())
		flag = 0
		if copy != check:
			flag = 1
		print(1 - flag)