Given an array arr of non-negative integers of size N, 2 players are playing a game. In each move, a player chooses an element from either end of the array, and the size of the array shrinks by one. Both players take alternate chances and the game continues until the size of the array becomes 0. Every time a player chooses an array element the array value is added to the player's score. At the end player with maximum score wins.
If player 1 starts the game, you have to predict whether player 1 will win the game or not. Both players will play optimally.
 
Example 1:
Input:
N = 3
arr[] = {2,6,3}
Output:
0 
Explanation:
Initially, player 1 can choose between 2 and 3. 
If he chooses 3 (or 2), then player 2 can choose 
from 2 (or 3) and 6. If player 2 chooses 6,
then player 1 will be left with 2 (or 3). 
So, final score of player 1 is 2 + 3 = 5,
and player 2 is 6. 
Hence, player 1 will never be the winner and 
output is 0.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function is1winner() which takes the array arr[], its size N and returns true if player 1 is the winner and false otherwise.
The driver code itself prints 1 if returned value is true and 0 otherwise.
Expected Time Complexity: O(N*N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 1000
0<= arr[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
    def is1winner (self, N, arr):
        # code here 
        
        

Solutions:
class Solution:

	def is1winner(self, N, arr):
		dp = [[-1 for i in range(len(arr))] for j in range(len(arr))]

		def playGame(l, r):
			if l > r:
				return 0
			if l == r:
				return arr[r]
			if dp[l][r] != -1:
				return dp[l][r]
			option1 = arr[l] + min(playGame(l + 2, r), playGame(l + 1, r - 1))
			option2 = arr[r] + min(playGame(l + 1, r - 1), playGame(l, r - 2))
			dp[l][r] = max(option1, option2)
			return dp[l][r]
		ans = playGame(0, len(arr) - 1)
		return int(ans > sum(arr) / 2)


class Solution:

	def is1winner(self, N, arr):
		dp = [[0] * N for _ in range(N)]
		summ = [0] * (N + 1)
		for i in range(N):
			summ[i + 1] = summ[i] + arr[i]
			dp[i][i] = arr[i]
		for k in range(1, N):
			i = 0
			while i + k < N:
				j = i + k
				total = summ[j + 1] - summ[i]
				dp[i][j] = total - min(dp[i + 1][j], dp[i][j - 1])
				i += 1
		return dp[0][N - 1] >= summ[N] - dp[0][N - 1]


from functools import lru_cache

class Solution:

	def is1winner(self, N, arr):
		tab = [[0] * (N + 1) for bla in range(N + 1)]
		for gap in range(1, N + 1):
			for x in range(N - gap + 1):
				y = x + gap
				tab[x][y] = max(arr[x] - tab[x + 1][y], arr[y - 1] - tab[x][y - 1])
		return tab[0][N] > 0


from functools import lru_cache

class Solution:

	def recSolver(self, arr):
		if arr in self.dct:
			return self.dct[arr]
		if len(arr) == 0:
			return 0
		if len(arr) == 1:
			return arr[0]
		(A, B) = (arr[0] - self.recSolver(arr[1:]), arr[-1] - self.recSolver(arr[:-1]))
		self.dct[arr] = max(A, B)
		return max(A, B)

	def is1winner(self, N, arr):
		tab = [[0] * (N + 1) for bla in range(N + 1)]
		for gap in range(1, N + 1):
			for x in range(N - gap + 1):
				y = x + gap
				(A, B) = (arr[x] - tab[x + 1][y], arr[y - 1] - tab[x][y - 1])
				tab[x][y] = max(A, B)
		return tab[0][N] > 0


class Solution:

	def solve(self, arr, i, j, dp):
		if i > j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		opt1 = arr[i] + min(self.solve(arr, i + 2, j, dp), self.solve(arr, i + 1, j - 1, dp))
		opt2 = arr[j] + min(self.solve(arr, i, j - 2, dp), self.solve(arr, i + 1, j - 1, dp))
		dp[i][j] = max(opt1, opt2)
		return dp[i][j]

	def is1winner(self, N, arr):
		dp = [[0 for i in range(N)] for j in range(N)]
		for i in range(N):
			k = 0
			for j in range(i, N):
				if i == 0:
					dp[k][j] = arr[k]
				elif i == 1:
					dp[k][j] = max(arr[k], arr[j])
				else:
					a1 = arr[k] + min(dp[k + 2][j], dp[k + 1][j - 1])
					a2 = arr[j] + min(dp[k + 1][j - 1], dp[k][j - 2])
					dp[k][j] = max(a1, a2)
				k += 1
		p1 = dp[0][N - 1]
		summ = sum(arr)
		return p1 > summ - p1


class Solution:

	def solve(self, arr, i, j, dp):
		if i > j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		opt1 = arr[i] + min(self.solve(arr, i + 2, j, dp), self.solve(arr, i + 1, j - 1, dp))
		opt2 = arr[j] + min(self.solve(arr, i, j - 2, dp), self.solve(arr, i + 1, j - 1, dp))
		dp[i][j] = max(opt1, opt2)
		return dp[i][j]

	def is1winner(self, N, arr):
		dp = [[-1 for _ in range(N)] for _ in range(N)]
		p1 = self.solve(arr, 0, N - 1, dp)
		summ = sum(arr)
		return p1 > summ - p1


class Solution:

	def is1winner(self, N, arr):
		dp = [[0 for i in range(N)] for j in range(N)]
		for gap in range(N):
			for i in range(N - gap):
				j = i + gap
				if i == j:
					dp[i][j] = arr[i]
				elif i + 1 == j:
					dp[i][j] = max(arr[i], arr[j])
				else:
					dp[i][j] = max(min(dp[i + 2][j], dp[i + 1][j - 1]) + arr[i], min(dp[i + 1][j - 1], dp[i][j - 2]) + arr[j])
		return dp[0][N - 1] > max(dp[1][N - 1], dp[0][N - 2])


class Solution:

	def is1winner(self, N, arr):
		dp = [[0 for i in range(N)] for j in range(N)]
		for i in range(N):
			k = 0
			for j in range(i, N):
				if i == 0:
					dp[k][j] = arr[k]
				elif i == 1:
					dp[k][j] = max(arr[k], arr[j])
				else:
					a1 = arr[k] + min(dp[k + 2][j], dp[k + 1][j - 1])
					a2 = arr[j] + min(dp[k + 1][j - 1], dp[k][j - 2])
					dp[k][j] = max(a1, a2)
				k += 1
		tot = sum(arr) - dp[0][N - 1]
		return True if dp[0][N - 1] > tot else False
		dp = [[-1 for i in range(N)] for j in range(N)]

		def solve(i, j):
			if i > j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			a1 = arr[i] + min(solve(i + 2, j), solve(i + 1, j - 1))
			a2 = arr[j] + min(solve(i, j - 2), solve(i + 1, j - 1))
			dp[i][j] = max(a1, a2)
			return dp[i][j]
		ans = solve(0, N - 1)
		tot = sum(arr)
		return True if ans > tot - ans else False


class Solution:

	def is1winner(self, N, nums):
		dp = [[0 for i in range(len(nums))] for j in range(len(nums))]
		for k in range(len(nums)):
			(i, j) = (0, k)
			while j < len(nums):
				if k == 0:
					dp[i][j] = nums[i]
				elif k == 1:
					dp[i][j] = max(nums[i], nums[j])
				else:
					dp[i][j] = max(nums[i] + min(dp[i + 2][j], dp[i + 1][j - 1]), nums[j] + min(dp[i][j - 2], dp[i + 1][j - 1]))
				i += 1
				j += 1
		total = sum(nums)
		return dp[0][-1] >= total - dp[0][-1]


import sys
sys.setrecursionlimit(10 ** 8)

class Solution2:

	def is1winner2(self, N, arr):
		(i, j) = (0, len(arr) - 1)
		mp = {}
		res = self.solve(arr, i, j, 0, mp)
		total = sum(arr)
		score_p1 = res
		score_p2 = total - res
		return True if score_p1 > score_p2 else False

	def solve(self, arr, i, j, chance, mp):
		if i > j:
			return 0
		if (i, j) in mp:
			return mp[i, j]
		if chance == 0:
			res1 = arr[i] + self.solve(arr, i + 1, j, 1, mp)
			res2 = arr[j] + self.solve(arr, i, j - 1, 1, mp)
			res = max(res1, res2)
		else:
			res1 = self.solve(arr, i + 1, j, 0, mp)
			res2 = self.solve(arr, i, j - 1, 0, mp)
			res = min(res1, res2)
		mp[i, j] = res
		return res
import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def is1winner(self, N, arr):
		dp = [[-1 for i in range(1001)] for j in range(1001)]

		def memo(start, end, chance):
			if start > end:
				return 0
			if dp[start][end] != -1:
				return dp[start][end]
			if chance == 0:
				left = arr[start] + memo(start + 1, end, chance ^ 1)
				right = arr[end] + memo(start, end - 1, chance ^ 1)
				dp[start][end] = max(left, right)
			else:
				left = memo(start + 1, end, chance ^ 1)
				right = memo(start, end - 1, chance ^ 1)
				dp[start][end] = min(left, right)
			return dp[start][end]
		a = sum(arr)
		b = memo(0, N - 1, 0)
		return b > a - b


class Solution:

	def recur(self, A, i, j, dp):
		try:
			if i == j:
				dp[i][j] = A[i]
				return dp[i][j]
			if dp[i][j] != -1:
				return dp[i][j]
			if i + 1 == j:
				dp[i][j] = max(A[i], A[j])
				return dp[i][j]
			start = A[i] + min(self.recur(A, i + 2, j, dp), self.recur(A, i + 1, j - 1, dp))
			end = A[j] + min(self.recur(A, i, j - 2, dp), self.recur(A, i + 1, j - 1, dp))
			dp[i][j] = max(start, end)
			return dp[i][j]
		except Exception as e:
			print('e', e)

	def is1winner(self, N, arr):
		dp = [[-1 for _ in range(N)] for _ in range(N)]
		sum_ = self.recur(arr, 0, N - 1, dp)
		m_sum = sum(arr)
		if m_sum - sum_ > sum_:
			return 0
		else:
			return 1


class Solution:

	def is1winner(self, N, arr):
		total_sum = sum(arr)
		front1 = [0] * N
		front2 = [0] * N
		for i in range(N - 1, -1, -1):
			curr = [0] * N
			for j in range(i, N):
				left = arr[i] + min(front1[j - 1], front2[j])
				right = arr[j] + min(front1[j - 1], curr[j - 2])
				curr[j] = max(left, right)
			front2 = front1
			front1 = curr
		return 1 if 2 * front1[N - 1] >= total_sum else 0


class Solution:

	def is1winner(self, N, arr):
		total_sum = sum(arr)
		dp = [[0] * N for _ in range(N + 2)]
		for i in range(N):
			dp[i][i] = arr[i]
		for i in range(N - 1, -1, -1):
			for j in range(i + 1, N):
				left = right = 0
				left = arr[i] + min(dp[i + 1][j - 1], dp[i + 2][j])
				right = arr[j] + min(dp[i + 1][j - 1], dp[i][j - 2])
				dp[i][j] = max(left, right)
		return 1 if 2 * dp[0][N - 1] >= total_sum else 0


class Solution:

	def is1winner(self, n, a):
		dp = [[0 for i in range(n)] for j in range(n)]
		for g in range(n):
			i = 0
			j = g
			while i < n and j < n:
				if g == 0:
					dp[i][j] = a[i]
				elif g == 1:
					dp[i][j] = max(a[i], a[j])
				else:
					z = a[i] + min(dp[i + 1][j - 1], dp[i + 2][j])
					x = a[j] + min(dp[i + 1][j - 1], dp[i][j - 2])
					dp[i][j] = max(z, x)
				i = i + 1
				j = j + 1
		sm = sum(a)
		w = dp[0][n - 1]
		d = sm - w
		if d > w:
			return 0
		return 1


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def is1winner(self, N, arr):
		dp = [[-1 for i in range(1001)] for j in range(1001)]

		def memo(start, end, chance):
			if start > end:
				return 0
			if dp[start][end] != -1:
				return dp[start][end]
			if chance == 0:
				left = arr[start] + memo(start + 1, end, chance ^ 1)
				right = arr[end] + memo(start, end - 1, chance ^ 1)
				dp[start][end] = max(left, right)
			else:
				left = memo(start + 1, end, chance ^ 1)
				right = memo(start, end - 1, chance ^ 1)
				dp[start][end] = min(left, right)
			return dp[start][end]
		a = sum(arr)
		b = memo(0, N - 1, 0)
		return b > a - b


class Solution:

	def is1winner(self, N, arr):
		if not arr:
			return
		if N == 1:
			return True
		dp = [[0] * N for _ in range(N)]
		for i in range(N):
			dp[i][i] = arr[i]
		for d in range(1, N):
			for i in range(N - d):
				j = i + d
				dp[i][j] = max(arr[i] - dp[i + 1][j], arr[j] - dp[i][j - 1])
		return dp[0][N - 1] >= 0


class Solution:

	def is1winner(self, N, arr):
		total = sum(arr)
		dp = [[0 for j in range(N)] for i in range(N)]
		for diff in range(N):
			for i in range(N - diff):
				j = i + diff
				if i == j:
					dp[i][j] = arr[i]
				elif i + 1 == j:
					dp[i][j] = max(arr[i], arr[j])
				else:
					dp[i][j] = max(arr[i] + min(dp[i + 2][j], dp[i + 1][j - 1]), arr[j] + min(dp[i][j - 2], dp[i + 1][j - 1]))
		return total - dp[0][N - 1] < dp[0][N - 1]


import sys
sys.setrecursionlimit(1000000)

class Solution:

	def is1winner(self, n, a):
		dp = [[-1] * n for i in range(n)]

		def solve(i, j, v):
			if i > j:
				return 0
			if i == j and v:
				return a[i]
			if dp[i][j] != -1:
				return dp[i][j]
			if v:
				dp[i][j] = max(a[i] + solve(i + 1, j, False), a[j] + solve(i, j - 1, False))
			else:
				dp[i][j] = min(solve(i + 1, j, True), solve(i, j - 1, True))
			return dp[i][j]
		dp[0][n - 1] = solve(0, n - 1, True)
		s = sum(a)
		if dp[0][n - 1] >= s // 2:
			return True
		else:
			return False


import sys

class Solution:

	def is1winner(self, N, arr):
		dp = [[-1 for i in range(N + 1)] for j in range(N + 1)]
		sum_ = sum(arr)
		result = self.__solve(arr, 0, N - 1, N, dp)
		opp_sc = sum_ - result
		if result > opp_sc:
			return 1
		return 0

	def __solve(self, arr, start, end, N, dp):
		if start >= end:
			if N % 2 == 0:
				return 0
			return arr[end]
		if dp[start][end] != -1:
			return dp[start][end]
		choose_first = arr[start] + min(self.__solve(arr, start + 2, end, N, dp), self.__solve(arr, start + 1, end - 1, N, dp))
		choose_last = arr[end] + min(self.__solve(arr, start + 1, end - 1, N, dp), self.__solve(arr, start, end - 2, N, dp))
		result = max(choose_first, choose_last)
		dp[start][end] = result
		return result


class Solution:

	def rec_pick(self, arr, i, j, mem):
		if i > j:
			return 0
		if mem[i][j] != -1:
			return mem[i][j]
		case1 = arr[i] + min(self.rec_pick(arr, i + 2, j, mem), self.rec_pick(arr, i + 1, j - 1, mem))
		case2 = arr[j] + min(self.rec_pick(arr, i, j - 2, mem), self.rec_pick(arr, i + 1, j - 1, mem))
		mem[i][j] = max(case1, case2)
		return mem[i][j]

	def is1winner(self, N, arr):
		mem = [[-1] * N for i in range(N)]
		p1 = self.rec_pick(arr, 0, N - 1, mem)
		if p1 > sum(arr) - p1:
			return True
		return False


class Solution:

	def is1winner(self, N, arr):
		if N % 2 != 0:
			return 0
		else:
			return 1


import sys
sys.setrecursionlimit(1000000)

def f(A, i, j, dp):
	if i > j:
		return 0
	if dp[i][j] != -1000000000.0:
		return dp[i][j]
	ans = max(A[i] - f(A, i + 1, j, dp), A[j] - f(A, i, j - 1, dp))
	dp[i][j] = ans
	return ans

def f2(A, i, j, dp):
	if i > j:
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	a = A[i] + min(f2(A, i + 1, j - 1, dp), f2(A, i + 2, j, dp))
	b = A[j] + min(f2(A, i + 1, j - 1, dp), f2(A, i, j - 2, dp))
	ans = max(a, b)
	dp[i][j] = ans
	return ans

class Solution:

	def is1winner(self, N, arr):
		dp = [[-1 for i in range(1001)] for i in range(1001)]
		summ = sum(arr)
		ans = f2(arr, 0, N - 1, dp)
		if summ - ans < ans:
			return True
		return False


import sys
sys.setrecursionlimit(1000000)

def f(A, i, j, dp):
	if i > j:
		return 0
	if dp[i][j] != -1000000000.0:
		return dp[i][j]
	ans = max(A[i] - f(A, i + 1, j, dp), A[j] - f(A, i, j - 1, dp))
	dp[i][j] = ans
	return ans

class Solution:

	def is1winner(self, N, arr):
		dp = [[-1000000000.0 for i in range(1001)] for i in range(1001)]
		return f(arr, 0, N - 1, dp) >= 0


class Solution:

	def is1winner(self, N, arr):

		def rec(start, end):
			if start > end:
				return 0
			if start == end:
				return arr[start]
			if dp[start][end] == -1:
				dp[start][end] = max(arr[start] + min(rec(start + 2, end), rec(start + 1, end - 1)), arr[end] + min(rec(start + 1, end - 1), rec(start, end - 2)))
			return dp[start][end]
		dp = [[-1] * N for i in range(N)]
		sumi = sum(arr)
		sumi1 = rec(0, N - 1)
		return sumi < 2 * sumi1


class Solution:

	def gold(self, l, r, arr, dp):
		if l > r:
			return 0
		if dp[l][r] != -1:
			return dp[l][r]
		left = arr[l] + min(self.gold(l + 2, r, arr, dp), self.gold(l + 1, r - 1, arr, dp))
		right = arr[r] + min(self.gold(l + 1, r - 1, arr, dp), self.gold(l, r - 2, arr, dp))
		dp[l][r] = max(left, right)
		return dp[l][r]

	def is1winner(self, n, arr):
		dp = [[-1 for i in range(n)] for j in range(n)]
		b = self.gold(0, n - 1, arr, dp)
		e = sum(arr)
		if e - b > b:
			return False
		return True


import sys
sys.setrecursionlimit(10 ** 6)

def fun_even(arr, i, j, dp):
	if i > j:
		return 0
	elif dp[i][j] != -1:
		return dp[i][j]
	else:
		if (j - i) % 2 != 0:
			dp[i][j] = max(arr[i] + fun_even(arr, i + 1, j, dp), arr[j] + fun_even(arr, i, j - 1, dp))
		else:
			dp[i][j] = min(fun_even(arr, i + 1, j, dp), fun_even(arr, i, j - 1, dp))
		return dp[i][j]

def fun_odd(arr, i, j, dp):
	if i > j:
		return 0
	elif dp[i][j] != -1:
		return dp[i][j]
	else:
		if (j - i) % 2 == 0:
			dp[i][j] = max(arr[i] + fun_odd(arr, i + 1, j, dp), arr[j] + fun_odd(arr, i, j - 1, dp))
		else:
			dp[i][j] = min(fun_odd(arr, i + 1, j, dp), fun_odd(arr, i, j - 1, dp))
		return dp[i][j]

class Solution:

	def is1winner(self, N, arr):
		sumi = sum(arr)
		dp = [[-1 for i in range(N + 1)] for j in range(N + 1)]
		if N % 2 == 0:
			if fun_even(arr, 0, N - 1, dp) >= sumi / 2:
				return 1
			else:
				return 0
		elif fun_odd(arr, 0, N - 1, dp) >= sumi / 2:
			return 1
		else:
			return 0


class Solution:

	def is1winner(self, N, arr):
		sm = 0
		for i in range(N):
			sm += arr[i]
		dp = [[0] * (N + 2) for _ in range(N + 2)]
		for i in range(N - 1, -1, -1):
			for j in range(N):
				if j >= i:
					dp[i][j] = max(arr[i] + min(dp[i + 1][j - 1], dp[i + 2][j]), arr[j] + min(dp[i + 1][j - 1], dp[i][j - 2]))
		one = dp[0][N - 1]
		if 2 * one > sm:
			return True
		return False


class Solution:

	def is1winner(self, N, a):
		(i, j) = (0, N - 1)
		dp = [[-1] * N for _ in range(N)]

		def win(i, j):
			if i > j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			x = a[i] + min(win(i + 2, j), win(i + 1, j - 1))
			y = a[j] + min(win(i, j - 2), win(i + 1, j - 1))
			dp[i][j] = max(x, y)
			return dp[i][j]
		mp = win(i, j)
		return 1 if mp > sum(a) - mp else 0


class Solution:

	def is1winner(self, N, arr):
		(i, j) = (0, N - 1)
		(p1, p2, f) = (0, 0, 0)
		while i <= j:
			if arr[i] > arr[j]:
				x = arr[i]
				i += 1
			else:
				x = arr[j]
				j -= 1
			if f == 0:
				p1 = x
				f = 1
			else:
				f = 0
				p2 = x
		return 1 if p1 > p2 else 0


class Solution:

	def is1winner(self, n, arr):
		dp = [[0 for _ in range(n)] for _ in range(n)]
		sum_memo = [0 for _ in range(n + 1)]
		for i in range(1, n + 1):
			sum_memo[i] = sum_memo[i - 1] + arr[i - 1]
		for i in range(n):
			dp[i][i] = arr[i]
		for i in range(1, n):
			for k in range(n - i):
				j = k + i
				dp[k][j] = max(sum_memo[j + 1] - sum_memo[k + 1] - dp[k + 1][j] + arr[k], sum_memo[j] - sum_memo[k] - dp[k][j - 1] + arr[j])
		return dp[0][n - 1] > sum_memo[-1] / 2


class Solution:

	def is1winner(self, N, arr):
		dp = []
		for i in range(N + 1):
			x = []
			for j in range(N + 1):
				x.append(-1)
			dp.append(x)

		def solve(i, j):
			if i > j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			res1 = arr[i] + min(solve(i + 2, j), solve(i + 1, j - 1))
			res2 = arr[j] + min(solve(i, j - 2), solve(i + 1, j - 1))
			res = dp[i][j] = max(res1, res2)
			return res
		play1 = solve(0, N - 1)
		sm = sum(arr)
		if play1 > sm - play1:
			return 1
		else:
			return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = input().split()
		for itr in range(N):
			arr[itr] = int(arr[itr])
		ob = Solution()
		if ob.is1winner(N, arr) == True:
			print(1)
		else:
			print(0)


class Solution:

	def solve(self, i, j, arr, dp):
		if i > j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		a = arr[i] + min(self.solve(i + 2, j, arr, dp), self.solve(i + 1, j - 1, arr, dp))
		b = arr[j] + min(self.solve(i + 1, j - 1, arr, dp), self.solve(i, j - 2, arr, dp))
		dp[i][j] = max(a, b)
		return dp[i][j]

	def is1winner(self, n, arr):
		dp = [[-1 for i in range(n)] for i in range(n)]
		player1 = self.solve(0, n - 1, arr, dp)
		total = sum(arr)
		player2 = total - player1
		if player1 > player2:
			return True
		else:
			return False
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = input().split()
		for itr in range(N):
			arr[itr] = int(arr[itr])
		ob = Solution()
		if ob.is1winner(N, arr) == True:
			print(1)
		else:
			print(0)


class Solution:

	def is1winner(self, n, a):
		l = [[0] * n for i in range(n)]
		for i in range(n):
			for j in range(n - i):
				if i == 0:
					l[j][j] = a[j]
				elif i == 1:
					l[j][j + 1] = max(a[j], a[j + 1])
				else:
					k = j + i
					l[j][k] = max(a[j] + min(l[j + 1][k - 1], l[j + 2][k]), a[k] + min(l[j + 1][k - 1], l[j][k - 2]))
		return 1 if l[0][n - 1] > sum(a) - l[0][n - 1] else 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = input().split()
		for itr in range(N):
			arr[itr] = int(arr[itr])
		ob = Solution()
		if ob.is1winner(N, arr) == True:
			print(1)
		else:
			print(0)


class Solution:

	def rec(self, i, j, arr):
		if i > j or j < 0 or i > len(arr) - 1:
			return 0
		lv = arr[i] + min(self.rec(i + 2, j, arr), self.rec(i + 1, j - 1, arr))
		rv = arr[j] + min(self.rec(i + 1, j - 1, arr), self.rec(i, j - 2, arr))
		return max(lv, rv)

	def mem(self, i, j, arr, dp):
		if i > j or j < 0 or i > len(arr) - 1:
			return 0
		if dp[i][j] != -1:
			return -1
		lv = arr[i] + min(self.mem(i + 2, j, arr, dp), self.mem(i + 1, j - 1, arr, dp))
		rv = arr[j] + min(self.mem(i + 1, j - 1, arr, dp), self.mem(i, j - 2, arr, dp))
		dp[i][j] = max(lv, rv)
		return dp[i][j]

	def is1winner(self, N, arr):
		if N % 2 == 0:
			return True
		amt = self.mem(0, N - 1, arr, [[-1 for _ in range(N)] for _ in range(N)])
		other = sum(arr) - amt
		if amt > other:
			return True
		return False
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = input().split()
		for itr in range(N):
			arr[itr] = int(arr[itr])
		ob = Solution()
		if ob.is1winner(N, arr) == True:
			print(1)
		else:
			print(0)


class Solution:

	def util(self, arr, i, j, dp):
		if i > j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		x = arr[i] + min(self.util(arr, i + 2, j, dp), self.util(arr, i + 1, j - 1, dp))
		y = arr[j] + min(self.util(arr, i + 1, j - 1, dp), self.util(arr, i, j - 2, dp))
		dp[i][j] = max(x, y)
		return dp[i][j]

	def is1winner(self, N, arr):
		dp = [[-1 for i in range(N)] for j in range(N)]
		x = self.util(arr, 0, N - 1, dp)
		s = 0
		for i in range(N):
			s += arr[i]
		if x > s - x:
			return True
		return False
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = input().split()
		for itr in range(N):
			arr[itr] = int(arr[itr])
		ob = Solution()
		if ob.is1winner(N, arr) == True:
			print(1)
		else:
			print(0)


class Solution:

	def is1winner(self, N, arr):
		dp = [[-1] * (N + 1) for i in range(N + 1)]

		def solve(i, j, dp):
			if i > j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			c1 = arr[i] + min(solve(i + 2, j, dp), solve(i + 1, j - 1, dp))
			c2 = arr[j] + min(solve(i, j - 2, dp), solve(i + 1, j - 1, dp))
			dp[i][j] = max(c1, c2)
			return dp[i][j]
		r = solve(0, N - 1, dp)
		if r > sum(arr) - r:
			return 1


class Solution:

	def is1winner(self, N, arr):

		def rec(i, j, dp):
			if i > j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			c1 = arr[i] + min(rec(i + 2, j, dp), rec(i + 1, j - 1, dp))
			c2 = arr[j] + min(rec(i, j - 2, dp), rec(i + 1, j - 1, dp))
			dp[i][j] = max(c1, c2)
			return dp[i][j]
		dp = [[-1] * N for _ in range(N)]
		r1 = rec(0, len(arr) - 1, dp)
		return r1 > sum(arr) - r1


class Solution:

	def is1winner(self, N, arr):
		dp = [0] * N
		for s in range(N, -1, -1):
			for e in range(s, N):
				if s == e:
					dp[s] = arr[s]
				else:
					a = arr[s] - dp[e]
					b = arr[e] - dp[e - 1]
					dp[e] = max(a, b)
		return dp[N - 1] >= 0


class Solution:

	def is1winner(self, N, arr):
		dp = [[0 for i in range(N)] for j in range(N)]
		for g in range(N):
			i = 0
			for j in range(g, N):
				if g == 0:
					dp[i][j] = arr[i]
				elif g == 1:
					dp[i][j] = max(arr[i], arr[j])
				else:
					val1 = arr[i] + min(dp[i + 2][j], dp[i + 1][j - 1])
					val2 = arr[j] + min(dp[i + 1][j - 1], dp[i][j - 2])
					dp[i][j] = max(val1, val2)
				i += 1
		p1 = dp[0][N - 1]
		s = sum(arr)
		p2 = s - p1
		return p1 > p2


class Solution:

	def recursion(self, N, arr, i, j, dp):
		if i > j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		ans1 = arr[i] + min(self.recursion(N, arr, i + 2, j, dp), self.recursion(N, arr, i + 1, j - 1, dp))
		ans2 = arr[j] + min(self.recursion(N, arr, i + 1, j - 1, dp), self.recursion(N, arr, i, j - 2, dp))
		ans = max(ans1, ans2)
		dp[i][j] = ans
		return ans

	def is1winner(self, N, arr):
		dp = []
		for i in range(N):
			col = []
			for j in range(N):
				col.append(-1)
			dp.append(col)
		ans = self.recursion(N, arr, 0, N - 1, dp)
		sum = 0
		for i in arr:
			sum += i
		if 2 * ans > sum:
			return True
		return False


dp = [[-1 for i in range(1001)] for j in range(1001)]

def solve(i, j, a):
	if i > j:
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	l = a[i] + min(solve(i + 2, j, a), solve(i + 1, j - 1, a))
	r = a[j] + min(solve(i, j - 2, a), solve(i + 1, j - 1, a))
	dp[i][j] = max(l, r)
	return dp[i][j]

class Solution:

	def is1winner(self, N, arr):
		p = sum(arr)
		q = solve(0, N - 1, arr)
		if p - q > q:
			return False
		return True


class Solution:

	def is1winner(self, N, arr):
		a = [[0] * N for _ in range(N)]
		for g in range(N):
			j = g
			for i in range(N - g):
				if g == 0:
					a[i][j] = arr[i]
				elif g == 1:
					a[i][j] = max(a[i + 1][j], a[i][j - 1])
				else:
					a[i][j] = max(min(a[i + 2][j], a[i + 1][j - 1]) + arr[i], min(a[i + 1][j - 1], a[i][j - 2]) + arr[j])
				j += 1
		S = sum(arr)
		return 0 if a[0][N - 1] < S / 2 else 1


class Solution:

	def is1winner(self, N, arr):

		def max_score(arr, i, j, dp):
			if i > j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			lr = arr[i] + min(max_score(arr, i + 2, j, dp), max_score(arr, i + 1, j - 1, dp))
			rr = arr[j] + min(max_score(arr, i, j - 2, dp), max_score(arr, i + 1, j - 1, dp))
			dp[i][j] = max(lr, rr)
			return dp[i][j]
		smm = sum(arr)
		dp = [[-1] * N for _ in range(N)]
		ret = max_score(arr, 0, N - 1, dp)
		return ret > smm - ret


def find(arr, i, j, dp):
	if i > j:
		return 0
	if dp[i][j] != -1:
		return dp[i][j]
	x = arr[i] + min(find(arr, i + 2, j, dp), find(arr, i + 1, j - 1, dp))
	y = arr[j] + min(find(arr, i + 1, j - 1, dp), find(arr, i, j - 2, dp))
	dp[i][j] = max(x, y)
	return dp[i][j]

class Solution:

	def is1winner(self, N, arr):
		dp = [[-1 for i in range(N)] for j in range(N)]
		sc1 = find(arr, 0, N - 1, dp)
		sc2 = sum(arr) - sc1
		if sc1 > sc2:
			return True
		else:
			return False


class Solution:
	global p
	p = [[-1 for i in range(1001)] for j in range(1001)]

	def solve(self, a, start, end):
		if start > end:
			p[start][end] = 0
			return 0
		if start == end:
			p[start][end] = a[end]
		if p[start][end] != -1:
			return p[start][end]
		f = a[start] + min(self.solve(a, start + 2, end), self.solve(a, start + 1, end - 1))
		l = a[end] + min(self.solve(a, start, end - 2), self.solve(a, start + 1, end - 1))
		p[start][end] = max(f, l)
		return p[start][end]

	def is1winner(self, n, a):
		summ = sum(a)
		p1 = self.solve(a, 0, n - 1)
		p2 = summ - p1
		if p1 > p2:
			return 1
		return 0


class Solution:

	def is1winner(self, n, a):
		dp = [[0 for j in range(n)] for i in range(n)]
		for g in range(n):
			for (i, j) in zip(range(n), range(g, n)):
				if g == 0:
					dp[i][j] = a[i]
				elif g == 1:
					dp[i][j] = max(a[i], a[j])
				else:
					dp[i][j] = max(a[i] + min(dp[i + 2][j], dp[i + 1][j - 1]), a[j] + min(dp[i][j - 2], dp[i + 1][j - 1]))
		return sum(a) - dp[0][n - 1] < dp[0][n - 1]


class Solution:

	def is1winner(self, N, arr):
		if N % 2 == 0:
			return True
		else:
			return False


class Solution:

	def is1winner(self, N, arr):
		n = N

		def predict(i, j, dp):
			if i > j:
				return 0
			if dp[i][j] != -1:
				return dp[i][j]
			choice1 = arr[i] + min(predict(i + 2, j, dp), predict(i + 1, j - 1, dp))
			choice2 = arr[j] + min(predict(i + 1, j - 1, dp), predict(i, j - 2, dp))
			dp[i][j] = max(choice1, choice2)
			return dp[i][j]
		dp = [[-1] * 1001 for _ in range(1001)]
		total = sum(arr)
		best = predict(0, n - 1, dp)
		if best >= total - best:
			return 1
		return 0


class Solution:

	def is1winner(self, N, arr):
		memo = [[-1 for i in range(N)] for j in range(N)]

		def util(s, e):
			if s > e:
				return 0
			if memo[s][e] != -1:
				return memo[s][e]
			takeleft = arr[s] + min(util(s + 2, e), util(s + 1, e - 1))
			takeright = arr[e] + min(util(s, e - 2), util(s + 1, e - 1))
			memo[s][e] = max(takeleft, takeright)
			return max(takeleft, takeright)
		taken = util(0, N - 1)
		total = sum(arr)
		if taken > total / 2:
			return True
		return False


class Solution:

	def Helper(self, i, j):
		if i == j:
			self.dp[i][j] = self.arr[i]
			return self.dp[i][j]
		if i == 1:
			self.dp[i][j] = max(self.arr[i], self.arr[j])
			return self.dp[i][j]
		if self.dp[i][j] != -1:
			return self.dp[i][j]
		else:
			a = self.arr[i] + min(self.Helper(i + 2, j), self.Helper(i + 1, j - 1))
			b = self.arr[j] + min(self.Helper(i + 1, j - 1), self.Helper(i, j - 2))
			self.dp[i][j] = max(a, b)
			return self.dp[i][j]

	def is1winner(self, N, arr):
		self.arr = arr
		self.N = N
		if N % 2 == 0:
			return True
		self.dp = []
		for i in range(N + 1):
			l1 = []
			for j in range(N + 1):
				l1.append(-1)
			self.dp.append(l1)
		res1 = self.Helper(0, N - 1)
		res2 = res1 * -1
		for i in range(N):
			res2 += self.arr[i]
		return res1 > res2


class Solution:

	def is1winner(self, N, arr):
		t = [[0 for i in range(N)] for i in range(N)]
		for i in range(N):
			t[i][i] = arr[i]
		for i in range(N - 1):
			t[i][i + 1] = max(arr[i], arr[i + 1])
		for l in range(3, N, 2):
			for i in range(N - l):
				j = i + l
				val1 = arr[i] + min(t[i + 2][j], t[i + 1][j - 1])
				val2 = arr[j] + min(t[i + 1][j - 1], t[i][j - 2])
				t[i][j] = max(val1, val2)
		if t[0][N - 1] > 0:
			return 1
		else:
			return 0


dp = [[-1 for _ in range(1001)] for _ in range(1001)]

class Solution:

	def func2(self, arr, start, end):
		if start > end:
			return 0
		if dp[start][end] != -1:
			return dp[start][end]
		left = arr[start] + min(self.func2(arr, start + 2, end), self.func2(arr, start + 1, end - 1))
		right = arr[end] + min(self.func2(arr, start + 1, end - 1), self.func2(arr, start, end - 2))
		dp[start][end] = max(left, right)
		return dp[start][end]

	def is1winner(self, N, arr):
		total_score = sum(arr)
		max_score_player1 = self.func2(arr, 0, N - 1)
		max_score_player2 = total_score - max_score_player1
		return max_score_player1 > max_score_player2


class Solution:

	def is1winner(self, N, arr):
		points = sum(arr)
		max_points = [[0 for j in range(N)] for i in range(N)]
		for i in range(N):
			max_points[i][i] = arr[i]
		for i in range(N - 1):
			max_points[i][i + 1] = max(arr[i], arr[i + 1])
		if N & 1:
			start = 2
		else:
			start = 3
		for gap in range(start, N, 2):
			l = 0
			r = gap
			while r < N:
				max_points[l][r] = max(arr[l] + min(max_points[l + 2][r], max_points[l + 1][r - 1]), arr[r] + min(max_points[l + 1][r - 1], max_points[l][r - 2]))
				l += 1
				r += 1
		return int(max_points[0][N - 1] >= points / 2)


class Solution:

	def is1winner(self, n, l):
		l1 = [[0] * n for i in range(n)]
		for i in range(n):
			for j in range(n - i):
				if i == 0:
					l1[j][j] = l[j]
				elif i == 1:
					l1[j][j + 1] = max(l[j], l[j + 1])
				else:
					k = j + i
					l1[j][k] = max(l[j] + min(l1[j + 1][k - 1], l1[j + 2][k]), l[k] + min(l1[j + 1][k - 1], l1[j][k - 2]))
		(z, s) = (l1[0][n - 1], sum(l))
		return 1 if z > s - z else 0


class Solution:

	def is1winner(self, N, arr):
		dp = [0] * N
		for i in range(N - 1, -1, -1):
			dp2 = [0] * N
			for j in range(i, N):
				dp2[j] = max(arr[i] - dp[j], arr[j] - (dp2[j - 1] if j else 0))
			dp = dp2
		ans = dp[N - 1]
		if ans >= 0:
			return True
		return False


class Solution:

	def is1winner(self, N, arr):
		dp = [[-1 for j in range(N)] for i in range(N)]
		t = self.helper(arr, 0, N - 1, dp)
		if t > sum(arr) - t:
			return True
		return False

	def helper(self, arr, i, j, dp):
		if i > j:
			return 0
		if dp[i][j] != -1:
			return dp[i][j]
		a = arr[i] + min(self.helper(arr, i + 2, j, dp), self.helper(arr, i + 1, j - 1, dp))
		b = arr[j] + min(self.helper(arr, i, j - 2, dp), self.helper(arr, i + 1, j - 1, dp))
		dp[i][j] = max(a, b)
		return dp[i][j]


class Solution:

	def is1winner(self, n, arr):
		score = self.dfs(0, n - 1, arr, {})
		return 1 if score > sum(arr) // 2 else 0

	def dfs(self, left, right, arr, cache):
		if left > right:
			return 0
		key = (left, right)
		if key in cache:
			return cache[key]
		even = (right - left) % 2
		cur_left_score = arr[left] if even else 0
		cur_right_score = arr[right] if even else 0
		left_score = cur_left_score + self.dfs(left + 1, right - 1, arr, cache)
		right_score = cur_right_score + self.dfs(left + 1, right - 1, arr, cache)
		cache[key] = max(left_score, right_score)
		return cache[key]


class Solution:

	def helper(self, arr, low, high, dp):
		if low > high:
			return 0
		if dp[low][high] != -1:
			return dp[low][high]
		choice1 = arr[low] + min(self.helper(arr, low + 2, high, dp), self.helper(arr, low + 1, high - 1, dp))
		choice2 = arr[high] + min(self.helper(arr, low + 1, high - 1, dp), self.helper(arr, low, high - 2, dp))
		dp[low][high] = max(choice1, choice2)
		return dp[low][high]

	def is1winnerRecursive(self, N, arr):
		dp = [[-1] * N for i in range(N)]
		t_sum = sum(arr)
		score = self.helper(arr, 0, N - 1, dp)
		if score >= t_sum - score:
			return True
		else:
			return False

	def is1winner(self, N, arr):
		t_sum = sum(arr)
		dp = [[0] * N for i in range(N)]
		for i in range(N):
			dp[i][i] = arr[i]
		for l in range(2, N + 1):
			for j in range(N - l + 1):
				start = j
				end = j + l - 1
				if l == 2:
					choice_1 = arr[start]
					choice_2 = arr[end]
				else:
					choice_1 = arr[start] + min(dp[start + 2][end], dp[start + 1][end - 1])
					choice_2 = arr[end] + min(dp[start + 1][end - 1], dp[start][end - 2])
				dp[start][end] = max(choice_1, choice_2)
		return dp[0][N - 1] > t_sum - dp[0][N - 1]


class Solution:

	def helper(self, arr, low, high, dp):
		if low > high:
			return 0
		if dp[low][high] != -1:
			return dp[low][high]
		choice1 = arr[low] + min(self.helper(arr, low + 2, high, dp), self.helper(arr, low + 1, high - 1, dp))
		choice2 = arr[high] + min(self.helper(arr, low + 1, high - 1, dp), self.helper(arr, low, high - 2, dp))
		dp[low][high] = max(choice1, choice2)
		return dp[low][high]

	def is1winner(self, N, arr):
		dp = [[-1] * N for i in range(N)]
		t_sum = sum(arr)
		score = self.helper(arr, 0, N - 1, dp)
		if score >= t_sum - score:
			return True
		else:
			return False


class Solution:

	def is1winner(self, n, arr):
		dp = [[0 for i in range(n)] for j in range(n)]
		for i in range(n - 1):
			dp[i][i + 1] = max(arr[i], arr[i + 1])
		for gap in range(3, n, 2):
			i = 0
			while i + gap < n:
				j = i + gap
				dp[i][j] = max(arr[i] + min(dp[i + 2][j], dp[i + 1][j - 1]), arr[j] + min(dp[i + 1][j - 1], dp[i][j - 2]))
				i += 1
		temp = sum(arr)
		if dp[0][n - 1] >= temp // 2:
			return True
		return False


class Solution:

	def is1winner(self, n, arr):
		dp = [[0 for j in range(n)] for i in range(n)]
		for g in range(n):
			i = 0
			j = g
			while j < n:
				if g == 0:
					dp[i][j] = arr[i]
				elif g == 1:
					dp[i][j] = max(arr[i], arr[j])
				else:
					ans1 = arr[i] + min(dp[i + 2][j], dp[i + 1][j - 1])
					ans2 = arr[j] + min(dp[i + 1][j - 1], dp[i][j - 2])
					dp[i][j] = max(ans1, ans2)
				i += 1
				j += 1
		sum = 0
		for ele in arr:
			sum += ele
		if dp[0][n - 1] > sum / 2:
			return True
		return False


class Solution:

	def is1winner(self, N, arr):
		dp = [0] * N
		for i in range(N - 2, -1, -1):
			dp[i] = arr[i]
			for j in range(i + 1, N):
				dp[j] = max(arr[i] - dp[j], arr[j] - dp[j - 1])
		if dp[-1] >= 0:
			return 1
		return 0


def optimalPlan(arr, i, j):
	global dp
	if i - j == 0:
		return arr[i]
	if j - i == 1:
		return max(arr[i], arr[j])
	if dp[i][j] != -1:
		return dp[i][j]
	k1 = arr[i] + min(optimalPlan(arr, i + 2, j), optimalPlan(arr, i + 1, j - 1))
	k2 = arr[j] + min(optimalPlan(arr, i + 1, j - 1), optimalPlan(arr, i, j - 2))
	dp[i][j] = max(k1, k2)
	return max(k1, k2)

def optimalPlanController(arr):
	global dp
	dp = [[-1 for i in range(len(arr))] for j in range(len(arr))]
	return optimalPlan(arr, 0, len(arr) - 1)

class Solution:

	def is1winner(self, N, arr):
		k1 = optimalPlanController(arr)
		k2 = sum(arr) - k1
		if k1 > k2:
			return 1
		return 0


import sys
sys.setrecursionlimit(1000000)

class Solution:

	def win(self, arr, dp, s, e):
		if s > e:
			return 0
		if dp[s][e] != -1000000000.0:
			return dp[s][e]
		a = arr[s] - self.win(arr, dp, s + 1, e)
		b = arr[e] - self.win(arr, dp, s, e - 1)
		dp[s][e] = max(a, b)
		return dp[s][e]

	def is1winner(self, N, arr):
		dp = [[-1000000000.0 for i in range(N)] for i in range(N)]
		return self.win(arr, dp, 0, N - 1) >= 0


class Solution:

	def is1winner(self, n, arr):
		if n <= 2:
			return 1
		dp = [[-1] * (n + 1) for i in range(n + 1)]

		def helper(i, j):
			if i > j:
				return 0
			if i == j:
				return arr[i]
			if dp[i][j] != -1:
				return dp[i][j]
			op1 = arr[i] + min(helper(i + 2, j), helper(i + 1, j - 1))
			op2 = arr[j] + min(helper(i, j - 2), helper(i + 1, j - 1))
			dp[i][j] = max(op1, op2)
			return dp[i][j]
		p1 = helper(0, n - 1)
		p2 = sum(arr) - p1
		if p1 > p2:
			return 1
		else:
			return 0


class Solution:

	def score(self, i, j, arr, dp):
		if i == j:
			return arr[i]
		if i + 1 == j:
			return max(arr[i], arr[j])
		if dp[i][j] != -1:
			return dp[i][j]
		dp[i][j] = max(arr[i] + min(self.score(i + 2, j, arr, dp), self.score(i + 1, j - 1, arr, dp)), arr[j] + min(self.score(i, j - 2, arr, dp), self.score(i + 1, j - 1, arr, dp)))
		return dp[i][j]

	def is1winner(self, N, arr):
		dp = [[-1] * (N + 1) for x in range(N + 1)]
		player1_score = self.score(0, N - 1, arr, dp)
		total = sum(arr)
		player2_score = total - player1_score
		if player1_score > player2_score:
			return True
		return False


class Solution:

	def is1winner(self, N, nums):
		dp = [[0] * len(nums) for _ in range(len(nums))]
		for s in range(len(nums)):
			for i in range(len(nums) - s):
				j = i + s
				if i == j:
					dp[i][i] = nums[i]
				else:
					dp[i][j] = max(nums[j] - dp[i][j - 1], nums[i] - dp[i + 1][j])
		return dp[0][-1] >= 0


def mgc(arr, i, j, dp):
	if i == j:
		return arr[i]
	if j == i + 1:
		return max(arr[i], arr[j])
	if dp[i][j] == -1:
		dp[i][j] = max(arr[i] + min(mgc(arr, i + 2, j, dp), mgc(arr, i + 1, j - 1, dp)), arr[j] + min(mgc(arr, i + 1, j - 1, dp), mgc(arr, i, j - 2, dp)))
	return dp[i][j]

class Solution:

	def is1winner(self, N, arr):
		dp = [[-1 for i in range(N + 1)] for j in range(N + 1)]
		x = sum(arr)
		temp = mgc(arr, 0, len(arr) - 1, dp)
		if x - temp > temp:
			return False
		return True


class Solution:

	def is1winner(self, N, nums):
		n = len(nums)
		dp = nums[:]
		for s in range(1, n):
			newdp = [0] * n
			for j in range(s, n):
				i = j - s
				newdp[j] = max(nums[i] - dp[j], nums[j] - dp[j - 1])
			dp = newdp
		return dp[-1] >= 0


class Solution:

	def is1winner(self, N, arr):
		nums = [[0 for _ in range(N)] for _ in range(N)]
		if N & 1:
			for i in range(N):
				nums[i][i] = arr[i]
		for i in range(N - 1, -1, -1):
			for j in range(i + 1, N):
				if j - i + 1 & 1 ^ N & 1:
					nums[i][j] = min(nums[i + 1][j], nums[i][j - 1])
				else:
					nums[i][j] = max(arr[i] + nums[i + 1][j], arr[j] + nums[i][j - 1])
		total = sum(arr)
		val = nums[0][N - 1]
		return int(val > total - val)


def win(i, j, arr, dp):
	if i > j:
		return 0
	elif dp[i][j] != -1:
		return dp[i][j]
	else:
		dp[i][j] = max(arr[i] + min(win(i + 1, j - 1, arr, dp), win(i + 2, j, arr, dp)), arr[j] + min(win(i + 1, j - 1, arr, dp), win(i, j - 2, arr, dp)))
		return dp[i][j]

class Solution:

	def is1winner(self, N, arr):
		dp = [[-1 for i in range(N)] for j in range(N)]
		ans = win(0, N - 1, arr, dp)
		if ans > sum(arr) - ans:
			return True
		else:
			return False