from os import *

from sys import *

from collections import *

from math import *

# Following is the Binary Tree node structure:

class BinaryTreeNode:

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

def leftBoundary(root, ans):

    if(root == None or (root.left == None and root.right == None)):

        return

    ans.append(root.data)

    if(root.left != None):

        leftBoundary(root.left, ans)

    else:

        leftBoundary(root.right, ans)

def traverseLeaf(root,ans):

    if root == None:return

    if root.left == None  and root.right== None: 

        ans.append(root.data)

        return  

    traverseLeaf(root.left,ans)

    traverseLeaf(root.right,ans)

def rightBoundary(root, ans):

    if(root == None or (root.left == None and root.right == None)):

        return

    if(root.right != None):

        rightBoundary(root.right, ans)

    else:

        rightBoundary(root.left, ans)

    ans.append(root.data)

def traverseBoundary(root):

    # Write your code here.

    ans =[]

    if root==None:return ans  

    ans.append(root.data)

    leftBoundary(root.left,ans)

    traverseLeaf(root.left,ans)

    traverseLeaf(root.right,ans)

    rightBoundary(root.right,ans)

    return ans

def reverseElements(q, k):

    # Write your code here

    # Return a queue

    n = q.qsize()

    # Maintain a array

    nums = [0 for i in range(n)]

    for i in range(0,n):

        nums[i] = q.get()

    num1 = nums[:k]

    num2 = nums[k:]

    nums = num1[::-1]+num2

    # Iterate i from 0 to N - 1

    for i in range(n):

        q.put(nums[i])

    # Return the queue containing elements in reverse order

    return q

def deleteMiddle(inputStack, N):

    # Write your solution here

    stack = []

    midIndex = int(N/2) 

    for i in range(midIndex+1):

        stack.append(inputStack[-1])

        inputStack.pop()

    stack = stack[::-1]

    for i in range(1,len(stack)):

        inputStack.append(stack[i])

    return inputStack

def searchInsert(arr: [int], m: int) -> int:

    # Write your code here.

    low = 0 

    high = len(arr) - 1

    while low <= high:

        mid = low + (high-low)//2 

        if arr[mid] == m:

            return mid 

        elif arr[mid] < m:

            low = mid + 1

        else:

            high = mid -1

    return low

def sumOfKxKMatrices(arr:list, k:int):

    n =len(arr)

    ans = [[0]*(n-k+1) for i in range(n-k+1)]

    prefix = [[0 for _ in range(n+1)] for _ in range(n+1)]

    for i in range(1,n+1):

        for j in range(1,n+1):

            prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + arr[i-1][j-1]

    for i in range(1,n-k+2):

        for j in range(1,n-k+2):

            ans[i-1][j-1] = prefix[i + k - 1][j + k - 1] - prefix[i - 1][j + k - 1] - prefix[i + k - 1][j - 1] + prefix[i - 1][j - 1]

    return ans 

def checkDuplicate(arr, n, k):   

    # Write your code here.

    mp = {}

    for i in range(len(arr)):

        if mp.get(arr[i],0) == 0:

            mp[arr[i]] =i + 1

        elif mp[arr[i]] > 0 and abs(mp[arr[i]] - (i+1)) <= k:

            return True  

        else:

            mp[arr[i]] = mp.get(arr[i],0) + i+1 

    return False 

def findTriplets(a, n):

    # Write your code here

    # Return a list of triplets

    res = []

    a.sort()

    for i in range(len(a)):

        if i >0 and a[i] == a[i-1]: continue

        left = i +1 

        right = n-1 

        while left < right:

            sum = a[i] + a[left] + a[right]

            if sum < 0:

                left += 1

            elif sum >0:

                right -= 1

            else:

                res.append([a[i],a[left],a[right]])

                left += 1

                while left < right and a[left] == a[left-1]:

                    left += 1

    return res

def maxSubarraySum(arr, n) :

    sum = 0 

    max_sum = 0

    if len(arr) == 0:

        return max_sum

    for i in range(len(arr)):

        sum += arr[i] 

        if sum < 0:

            sum = 0

        max_sum = max(max_sum,sum) 

    return max_sum