func numRescueBoats(people []int, limit int) int {
    sort.Ints(people)

    numberOfBouts := 0

    start := 0
    end := len(people)-1

    for start < end {
        if people[start] + people[end] <= limit {
            numberOfBouts++
            start++
        }else{
            numberOfBouts++
        }
        end--
    }

    if start == end {
        numberOfBouts++
    }

    return numberOfBouts
}

func compareVersion(version1 string, version2 string) int {

	rev1 := strings.Split(version1, ".")
	rev2 := strings.Split(version2, ".")
    // fmt.Println(rev1, rev2)

	revInt1 := make([]int, len(rev1))
	revInt2 := make([]int, len(rev2))

	for i := 0; i < len(rev1); i++ {
		revInt1[i], _ = strconv.Atoi(rev1[i])
	}
	for i := 0; i < len(rev2); i++ {
		revInt2[i], _ = strconv.Atoi(rev2[i])
	}
    // fmt.Println(revInt1, revInt2)

	i := 0
	j := 0

	for i < len(revInt1) && j < len(revInt2) {

		if revInt1[i] < revInt2[j] {
			return -1
		} else if revInt1[i] > revInt2[j] {
			return 1
		}
		i++
		j++
	}

	for i < len(revInt1) {
		if revInt1[i] > 0 {
			return 1
		}
		i++
	}
	for j < len(revInt2) {
		if revInt2[j] > 0 {
			return -1
		}
		j++
	}
	return 0
}

func findMaxK(nums []int) int {
    alreadySeenNums := map[int]bool{}
    res := -1

    for _, num := range nums {
        numAbs := int(math.Abs(float64(num)))

        if numAbs < res {
            continue
        }

        if alreadySeenNums[-num] {
            res = numAbs
        } else {
            alreadySeenNums[num] = true
        }
    }

    return res
}

type UnionFind struct {
    parent []int
    rank   []int
}

func NewUnionFind(n int) *UnionFind {
    parent := make([]int, n)
    rank := make([]int, n)
    for i := 0; i < n; i++ {
        parent[i] = i
    }
    return &UnionFind{parent, rank}
}

func (uf *UnionFind) Find(u int) int {
    if uf.parent[u] != u {
        uf.parent[u] = uf.Find(uf.parent[u])
    }
    return uf.parent[u]
}

func (uf *UnionFind) UnionByRank(u, v int) {
    i := uf.Find(u)
    j := uf.Find(v)
    if i == j {
        return
    }
    if uf.rank[i] < uf.rank[j] {
        uf.parent[i] = j
    } else if uf.rank[i] > uf.rank[j] {
        uf.parent[j] = i
    } else {
        uf.parent[i] = j
        uf.rank[j]++
    }
}

func validPath(n int, edges [][]int, source int, destination int) bool {
    uf := NewUnionFind(n)
    for _, edge := range edges {
        u, v := edge[0], edge[1]
        uf.UnionByRank(u, v)
    }
    return uf.Find(source) == uf.Find(destination)
}

func get(c rune) int {

    return int(c - 'a')

}



func wonderfulSubstrings(word string) int64 {

    cnt := make([]int64, 1024)

    cnt[0] = 1



    curState := 0

    res := int64(0)



    for _, c := range word {

        curState ^= 1 << get(c)



        res += cnt[curState]

        for odd := 'a'; odd <= 'j'; odd++ {

            oddState := curState ^ (1 << get(odd))

            res += cnt[oddState]

        }



        cnt[curState]++

    }



    return res

}

func sumOfDistancesInTree(n int, edges [][]int) []int {
	graph := make(map[int][]int)
	count := make([]int, n)
	res := make([]int, n)

	for _, edge := range edges {
		u, v := edge[0], edge[1]
		graph[u] = append(graph[u], v)
		graph[v] = append(graph[v], u)
	}

	var dfs1 func(cur, parent int)
	dfs1 = func(cur, parent int) {
		count[cur] = 1
		for _, child := range graph[cur] {
			if child != parent {
				dfs1(child, cur)
				count[cur] += count[child]
				res[cur] += res[child] + count[child]
			}
		}
	}

	var dfs2 func(cur, parent int)
	dfs2 = func(cur, parent int) {
		for _, child := range graph[cur] {
			if child != parent {
				res[child] = res[cur] + n - 2*count[child]
				dfs2(child, cur)
			}
		}
	}

	dfs1(0, -1)
	dfs2(0, -1)

	return res
}

func reversePrefix(word string, ch byte) string {
    var natija string
    for i := 0; i < len(word); i++ {
        if word[i] == ch { 
            ch_index := i
            for i >= 0 {
                natija += string(word[i])
                i--
            } 
            return natija + word[ch_index + 1 : ]
        }
    }    
    return word
}

func minOperations(nums []int, k int) int {
    res := k
    for _, n := range nums {
        res ^= n
    }
    var ans int
    for res > 0 {
        ans += res%2
        res = res >> 1
    }
    return ans
}

type Triplet struct {
	minSum       int
	secondMinSum int
	minSumIndex  int
}

func minFallingPathSum(grid [][]int) int {
	return minFallingPathSumHelper(0, grid).minSum
}

func minFallingPathSumHelper(row int, grid [][]int) Triplet {
	if row == len(grid) {
		return Triplet{0, 0, 0}
	}

	nextRowTriplet := minFallingPathSumHelper(row+1, grid)
	currentTriplet := Triplet{math.MaxInt32, math.MaxInt32, -1}

	for col := 0; col < len(grid[0]); col++ {
		var value int
		if col != nextRowTriplet.minSumIndex {
			value = grid[row][col] + nextRowTriplet.minSum
		} else {
			value = grid[row][col] + nextRowTriplet.secondMinSum
		}

		if value <= currentTriplet.minSum {
			currentTriplet.secondMinSum = currentTriplet.minSum
			currentTriplet.minSum = value
			currentTriplet.minSumIndex = col
		} else if value < currentTriplet.secondMinSum {
			currentTriplet.secondMinSum = value
		}
	}

	return currentTriplet
}

func longestIdealString(s string, k int) int {
	dp := make([]int, 27)
	n := len(s)

	for i := n - 1; i >= 0; i-- {
		cc := s[i]
		idx := int(cc - 'a')
		maxi := -1 << 31

		left := max(idx-k, 0)
		right := min(idx+k, 26)

		for j := left; j <= right; j++ {
			maxi = max(maxi, dp[j])
		}

		dp[idx] = maxi + 1
	}

	max := -1 << 31
	for _, val := range dp {
		if val > max {
			max = val
		}
	}

	return max
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func tribonacci(n int) int {
	if n < 2 {
		return n
	}

	dp := []int{0, 1, 1}

	for i := 3; i <= n; i++ {
		next := dp[0] + dp[1] + dp[2]
		dp[0], dp[1], dp[2] = dp[1], dp[2], next
	}

	return dp[2]
}

func findMinHeightTrees(n int, edges [][]int) []int {
	counts := make([]int, n)
	links := make([]int, n)
	for _, edge := range edges {
		links[edge[0]] ^= edge[1]
		counts[edge[0]]++
		links[edge[1]] ^= edge[0]
		counts[edge[1]]++
	}
	Qu := make([]int, 0)
	dists := make([]int, n)
	for i := 0; i < n; i++ {
		if counts[i] == 1 {
			Qu = append(Qu, i)
		}
	}
	stp := 1
	for len(Qu) > 0 {
		size := len(Qu)
		for j := 0; j < size; j++ {
			tmp := Qu[0]
			Qu = Qu[1:]
			links[links[tmp]] ^= tmp
			counts[links[tmp]]--
			if counts[links[tmp]] == 1 {
				dists[links[tmp]] = int(math.Max(float64(stp), float64(dists[links[tmp]])))
				Qu = append(Qu, links[tmp])
			}
		}
		stp++
	}
	maxDist := 0
	for _, dist := range dists {
		if dist > maxDist {
			maxDist = dist
		}
	}
	res := make([]int, 0)
	for i, dist := range dists {
		if dist == maxDist {
			res = append(res, i)
		}
	}
	return res
}

type UnionFind struct {
    parent []int
    rank   []int
}

func NewUnionFind(n int) *UnionFind {
    parent := make([]int, n)
    rank := make([]int, n)
    for i := 0; i < n; i++ {
        parent[i] = i
    }
    return &UnionFind{parent, rank}
}

func (uf *UnionFind) Find(u int) int {
    if uf.parent[u] != u {
        uf.parent[u] = uf.Find(uf.parent[u])
    }
    return uf.parent[u]
}

func (uf *UnionFind) UnionByRank(u, v int) {
    i := uf.Find(u)
    j := uf.Find(v)
    if i == j {
        return
    }
    if uf.rank[i] < uf.rank[j] {
        uf.parent[i] = j
    } else if uf.rank[i] > uf.rank[j] {
        uf.parent[j] = i
    } else {
        uf.parent[i] = j
        uf.rank[j]++
    }
}

func validPath(n int, edges [][]int, source int, destination int) bool {
    uf := NewUnionFind(n)
    for _, edge := range edges {
        u, v := edge[0], edge[1]
        uf.UnionByRank(u, v)
    }
    return uf.Find(source) == uf.Find(destination)
}

import "strconv"

func openLock(deadends []string, target string) int {
    pow10 := []int{1, 10, 100, 1000}
    visit := make([]int, 10000) // 0: not visited, 1: visited through forward direction, -1: visited through backward direction, 2: deadends
    for _, dead := range deadends {
        num, _ := strconv.Atoi(dead)
        visit[num] = 2
    }
    src := 0
    dest, _ := strconv.Atoi(target)
    steps := 0
    dir := 1
    if visit[src] == 2 || visit[dest] == 2 {
        return -1
    }
    if src == dest {
        return 0
    }
    forward := make([]int, 0)
    backward := make([]int, 0)
    forward = append(forward, src)
    visit[src] = 1
    backward = append(backward, dest)
    visit[dest] = -1
    for len(forward) > 0 && len(backward) > 0 {
        if len(forward) > len(backward) {
            forward, backward = backward, forward
            dir = -dir
        }
        steps++
        size := len(forward)
        for j := 0; j < size; j++ {
            cur := forward[0]
            forward = forward[1:]
            for _, p := range pow10 {
                d := (cur / p) % 10
                for _, i := range []int{-1, 1} {
                    z := d + i
                    if z == -1 {
                        z = 9
                    } else if z == 10 {
                        z = 0
                    }
                    next := cur + (z-d)*p
                    if visit[next] == -dir {
                        return steps
                    }
                    if visit[next] == 0 {
                        forward = append(forward, next)
                        visit[next] = dir
                    }
                }
            }
        }
    }
    return -1
}

func findFarmland(land [][]int) [][]int {
	result := [][]int{}
	m, n := len(land), len(land[0])
	findFarmlandCoordinates := func(row, col int) []int {
		coordinates := []int{row, col}
		r, c := row, col
		for r < m && land[r][col] == 1 {
			r++
		}
		for c < n && land[row][c] == 1 {
			c++
		}
		coordinates = append(coordinates, r-1, c-1)
		for i := row; i < r; i++ {
			for j := col; j < c; j++ {
				land[i][j] = 0
			}
		}
		return coordinates
    }
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if land[i][j] == 1 {
				result = append(result, findFarmlandCoordinates(i, j))
			}
		}
	}
	return result
}

func islandPerimeter(grid [][]int) int {
    islands := 0
    neighbors := 0

    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == 1 {
                islands++
                if i-1 >= 0 && grid[i-1][j] == 1 {
                    neighbors++
                }
                if j-1 >= 0 && grid[i][j-1] == 1 {
                    neighbors++
                }
            }
        }
    }

    return islands*4 - neighbors*2
}

func numIslands(grid [][]byte) int {
    if len(grid) == 0 || len(grid[0]) == 0 {
        return 0
    }
    
    rows := len(grid)
    cols := len(grid[0])
    islands := 0
    
    var dfs func(row, col int)
    dfs = func(row, col int) {
        if row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] != '1' {
            return
        }
        grid[row][col] = '0'
        dfs(row-1, col)
        dfs(row+1, col)
        dfs(row, col-1)
        dfs(row, col+1)
    }
    
    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            if grid[row][col] == '1' {
                dfs(row, col)
                islands++
            }
        }
    }
    
    return islands
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func smallestFromLeaf(root *TreeNode) string {
	ans := ""
	var dfs func(node *TreeNode, text string)
	dfs = func(node *TreeNode, text string) {
		if node == nil {
			return
		}
		text = string(rune(node.Val + 97)) + text
		if node.Right == nil && node.Left == nil {
			if ans == "" || ans > text {
				ans = text
			}
			return
		}
		dfs(node.Left, text)
		dfs(node.Right, text)
	}

	dfs(root, "")
	return ans
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func addOneRow(root *TreeNode, val int, depth int) *TreeNode {
    if root == nil {
        return nil
    }

    if depth == 1 {
        root = &TreeNode{Val: val, Left: root}
    } else if (depth == 2) {
        root.Left = &TreeNode{Val: val, Left: root.Left}
        root.Right = &TreeNode{Val: val, Right: root.Right}
    } else {
        addOneRow(root.Left, val, depth - 1)
        addOneRow(root.Right, val, depth - 1)
    }

    return root;
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumNumbers(root *TreeNode) int {
    return dfs(root, 0)
}

func dfs(node *TreeNode, num int) int {
    if node == nil {
        return 0
    }
    if node.Left == nil && node.Right == nil {
        return num * 10 + node.Val
    }
    return dfs(node.Left, num * 10 + node.Val) + dfs(node.Right, num * 10 + node.Val)
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumOfLeftLeaves(root *TreeNode) int {
    if root == nil {
        return 0
    }

    left := 0
    if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil {
        left = root.Left.Val
    }

    return left + sumOfLeftLeaves(root.Left) + sumOfLeftLeaves(root.Right)
}

func maximalRectangle(matrix [][]byte) int {
    heights := make([]int, len(matrix[0]) + 1)
    heights[len(heights)-1] = -1
    mx := 0
    for _, row := range matrix {
        for i := range row {
            if row[i] == '1' {
                heights[i]++
            } else {
                heights[i] = 0
            }
        }

        stack := []int{}
        for i, currentHeight := range heights {
            for len(stack) > 0 && heights[stack[len(stack)-1]] > currentHeight {
                prev := heights[stack[len(stack)-1]]
                stack = stack[:len(stack)-1]

                width := i
                if len(stack) > 0 {
                    width = i - stack[len(stack)-1] - 1
                }
                mx = max(mx, prev * width)
            }
            stack = append(stack, i)
        } 
    }
    return mx
}

func trap(height []int) int {
	var waterStored int
	leftElevationPoint, rightElevationPoint := 0, len(height)-1                                    // pointers for left and right elevations
	maxLeftElevation, maxRightElevation := height[leftElevationPoint], height[rightElevationPoint] // max value of left and right elevation points

	for leftElevationPoint < rightElevationPoint { // until left elevation point reaches right elevation point or right elevation point reaches left elevation point
		if maxLeftElevation < maxRightElevation { // if max left elevation is smaller than max right elevation
			leftElevationPoint++                               // move the left elevation point by 1
			if height[leftElevationPoint] > maxLeftElevation { // if height of current left elevation after moving is greater than max left elevation
				maxLeftElevation = height[leftElevationPoint] // swap the max left elevation with current left elevation point value
			}
			waterStored += maxLeftElevation - height[leftElevationPoint] // store water with delta of max left elevation and current left elevation
		} else {
			rightElevationPoint--                                // decrease the right elevation by 1
			if height[rightElevationPoint] > maxRightElevation { // if height of current right elevation after decreasing is greater than max right elevation
				maxRightElevation = height[rightElevationPoint] // swap the max right elevation with current right elevation point value
			}
			waterStored += maxRightElevation - height[rightElevationPoint] // store water with delta of max right elevation and current right elevation
		}
	}

	return waterStored
}

func removeKdigits(num string, k int) string {
	res := make([]rune, 0)
    
	for _, c := range num {
		for len(res) > 0 && res[len(res) - 1] > c && k > 0 {
			res = res[:len(res) - 1]
			k--
		}

		if len(res) > 0 || c != '0' {
			res = append(res, c)
		}
	}

	for len(res) > 0 && k > 0 {
		res = res[:len(res) - 1]
		k--
	}

	if len(res) == 0 {
		return "0"
	}
	return string(res)
}

func deckRevealedIncreasing(deck []int) []int {
	n := len(deck)
	sort.Ints(deck)

	res := make([]int, n)
	queue := make([]int, n)

	for i := range queue {
		queue[i] = i
	}

	for _, card := range deck {
		idx := queue[0]
		queue = queue[1:]
		res[idx] = card

		if len(queue) > 0 {
			queue = append(queue, queue[0])
			queue = queue[1:]
		}
	}

	return res
}

func timeRequiredToBuy(tickets []int, k int) int {
    n := len(tickets)
    d := tickets[k]
    res := 0
    for i := 0; i <= k; i++ {
        res += min(d, tickets[i])
    }
    for i := k + 1; i < n; i++ {
        res += min(d - 1, tickets[i])
    }
    return res
}

func countStudents(students []int, sandwiches []int) int {
    req := make([]int, 2)
    for _, student := range students {
        req[student]++
    }

    for _, sandwich := range sandwiches {
        if req[sandwich] == 0 {
            return req[1 - sandwich]
        } else {
            req[sandwich]--
        }
    }

    return 0
}

func checkValidString(s string) bool {
    open := 0
    openMax := 0
    for _, char := range s {
        switch char {
        case '(':
            open++
            openMax++
        case ')':
            open--
            openMax--
        default:
            open--
            openMax++
        }
        if openMax < 0 {
            return false
        }
        if open < 0 {
            open = 0
        }
    }
    return open == 0
}

type stack struct {
    top   int
    v     []byte
    index []int
}

func minRemoveToMakeValid(s string) string {
    stc := stack{top: -1}

    // collect bad brackets
    for i, v := range s {
        if v == '(' {
            stc.v = append(stc.v, '(')
            stc.index = append(stc.index, i)
            stc.top++
        } else if v == ')' {
            if stc.top > -1 && stc.v[stc.top] == '(' {
                stc.v = stc.v[:stc.top]
                stc.index = stc.index[:stc.top]
                stc.top--
            } else {
                stc.v = append(stc.v, ')')
                stc.index = append(stc.index, i)
                stc.top++
            }
        }
    }

    // remove them
    res := []byte{}
    i := 0
    for _, v := range stc.index {
        res = append(res, s[i:v]...)
        i = v + 1
    }

    // checking of end
    if len(res) + len(stc.index) < len(s) {
        res = append(res, s[i:]...)
    }

    return string(res)
}

func makeGood(s string) string {
	stack := make([]byte, 0, len(s))
	stack = append(stack, s[0])
	for i := 1; i < len(s); i++ {
		if len(stack) > 0 && getDiff(stack[len(stack)-1], s[i]) == 32 {
			stack = stack[:len(stack)-1]
			continue
		}
		stack = append(stack, s[i])
	}
	return string(stack)
}

func getDiff(a, b uint8) uint8 {
	if b > a {
		return b - a
	}
	return a - b
}

func maxDepth(s string) int {
    maxDepth := 0
    curDepth := 0
    for _, ch := range s {
        if ch == '(' {
            curDepth++
            maxDepth = max(maxDepth, curDepth)
        } else if ch == ')' {
            curDepth--
        }
    }
    return maxDepth
}

func exist(board [][]byte, word string) bool {
    if nLetters := len(board) * len(board[0]); nLetters < len(word) {
        return false
    }

    for i := range board {
        for j := range board[i] {
            if dfs(i, j, 0, board, word, make(map[pair]struct{})) {
                return true
            }
        }
    }

    return false
}

type pair struct {
    r, c int
}

func dfs(r, c, i int, board [][]byte, word string, visited map[pair]struct{}) bool {
    if i == len(word) {
        return true
    }

    inBounds := r >= 0 && r < len(board) && c >= 0 && c < len(board[0])
    if _, ok := visited[pair{r, c}]; !inBounds || ok || word[i] != board[r][c] {
        return false
    }

    visited[pair{r, c}] = struct{}{}

    up := dfs(r+1, c, i+1, board, word, visited)
    down := dfs(r-1, c, i+1, board, word, visited)
    right := dfs(r, c+1, i+1, board, word, visited)
    left := dfs(r, c-1, i+1, board, word, visited)

    delete(visited, pair{r, c})

    return up || down || right || left
}

func isIsomorphic(s string, t string) bool {
    map1 := make([]int, 128) // Stores frequency of s
    map2 := make([]int, 128) // Stores frequency of t

    for i := 0; i < len(s); i++ {
        sCh := s[i]
        tCh := t[i]

        if map1[sCh] == 0 && map2[tCh] == 0 {
            map1[sCh] = int(tCh)
            map2[tCh] = int(sCh)
        } else if map1[sCh] != int(tCh) || map2[tCh] != int(sCh) {
            return false
        }
    }
    return true
}

func lengthOfLastWord(s string) int {
    length := len(s)
    count := 0
    for i := length - 1; i >= 0; i-- {
        isSpace := s[i] == ' '
        if isSpace && count != 0 {
            return count
        } else if isSpace {
            continue
        }
        count++
    }
    return count
}

func countSubarrays(nums []int, minK int, maxK int) int64 {
    var res int64
	left := 0
	pmin := -1
	pmax := -1

	for right, num := range nums {
		if num < minK || num > maxK {
			left = right + 1
			pmin = -1
			pmax = -1
		} else {
			if num == minK {
				pmin = right
			}
			if num == maxK {
				pmax = right
			}
			res += int64(max(0, min(pmin, pmax) - left + 1))
		}
	}

	return res
}

func subarraysWithAtMostKDistinct(nums []int, k int) int {
    if k == 0 {
        return 0
    }

    countOccurrence := make(map[int]int)
    differentIntegers := 0
    left := 0
    result := 0

    for right := 0; right < len(nums); right++ {
        countOccurrence[nums[right]]++
        if countOccurrence[nums[right]] == 1 {
            differentIntegers++
        }

        for differentIntegers > k {
            countOccurrence[nums[left]]--
            if countOccurrence[nums[left]] == 0 {
                differentIntegers--
            }
            left++
        }

        result += right - left + 1
    }
    return result
}

func subarraysWithKDistinct(nums []int, k int) int {
    return subarraysWithAtMostKDistinct(nums, k) - subarraysWithAtMostKDistinct(nums, k-1)
}

func countSubarrays(nums []int, k int) int64 {
	maxValue := 0
	var maxValueIds []int
	var ans int64

	for i, x := range nums {
		if x > maxValue {
			maxValue, ans, maxValueIds = x, 0, []int{}
		}

		if x == maxValue {
			maxValueIds = append(maxValueIds, i)
		}

		if len(maxValueIds) >= k {
			ans += int64(maxValueIds[len(maxValueIds)-k]) + 1
		}
	}

	return ans
}

func maxSubarrayLength(nums []int, k int) int {
    i := 0
    j := 0
    n := len(nums)
    ans := 1
    mp := make(map[int]int)

    for i < n {
        mp[nums[i]]++
        for mp[nums[i]] > k {
            mp[nums[j]]--
            j++
        }
        if i-j+1 > ans {
            ans = i - j + 1
        }
        i++
    }
    return ans
}

func numSubarrayProductLessThanK(nums []int, k int) int {
	if k <= 1 {
		return 0
	}

	l := 0
	p := 1
	res := 0
	for r, num := range nums {
		p *= num
		for p >= k {
			p /= nums[l]
			l++
		}
        
		res += r - l + 1
	}

	return res
}

func firstMissingPositive(nums []int) int {
    n := len(nums)

	for i := 0; i < n; i++ {
		if nums[i] <= 0 || nums[i] > n {
			nums[i] = n + 1
		}
	}

	for i := 0; i < n; i++ {
		val := abs(nums[i])
		if val >= 1 && val <= n {
			flagIndex := val - 1
			if nums[flagIndex] > 0 {
				nums[flagIndex] *= -1
			}
		}
	}

	for i := 1; i <= n; i++ {
		if nums[i - 1] > 0 {
			return i
		}
	}

	return n + 1
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func findDuplicates(nums []int) []int {
    output := []int{}
    for _, num := range nums {
        idx := abs(num)
        if nums[idx-1] < 0 {
            output = append(output, idx)
        } else {
            nums[idx-1] *= -1
        }
    }
    return output
}
func abs(num int) int {
    if num < 0 {
        return -num
    }
    return num
}

func findDuplicate(nums []int) int {
    seen := make(map[int]struct{})
    for _, num := range nums {
        if _, ok := seen[num]; ok {
            return num
        }
        seen[num] = struct{}{}
    }
    return -1
}

func findDuplicate(nums []int) int {
    seen := make(map[int]struct{}, len(nums) - 1)
    for _, num := range nums {
        if _, ok := seen[num]; ok {
            return num
        }
        seen[num] = struct{}{}
    }
    return -1
}

func reorderList(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }

    middle := midNode(head)
    newHead := middle.Next
    middle.Next = nil

    newHead = reverseLinkedList(newHead)

    c1 := head
    c2 := newHead
    var f1, f2 *ListNode

    for c1 != nil && c2 != nil {
        // Backup
        f1 = c1.Next
        f2 = c2.Next

        // Linking
        c1.Next = c2
        c2.Next = f1

        // Move
        c1 = f1
        c2 = f2
    }
}

func midNode(head *ListNode) *ListNode {
    slow := head
    fast := head

    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

func reverseLinkedList(head *ListNode) *ListNode {
    var prev, curr, forw *ListNode = nil, head, nil

    for curr != nil {
        forw = curr.Next
        curr.Next = prev
        prev = curr
        curr = forw
    }
    return prev
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    nodes := []int{}
    for head != nil {
        nodes = append(nodes, head.Val)
        head = head.Next
    }
    length := len(nodes)
    for i := range(length / 2) {
        start, end := nodes[i], nodes[length-i-1]
        if start != end {
            return false
        }
    }
    return true
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    cur, next := head, head.Next
    head.Next = nil
    for next != nil {
        cur, next, next.Next = next, next.Next, cur
    }
    return cur
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    cur, next := head, head.Next
    head.Next = nil
    for next != nil {
        cur, next, next.Next = next, next.Next, cur
    }
    return cur
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    cur, next := head, head.Next
    cur.Next = nil
    for next != nil {
        cur, next, next.Next = next, next.Next, cur
    }
    return cur
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode {
    if list1 == nil {
        return list2 
    }
    list2Head, list2Tail := list2, list2
    for list2 != nil {
        list2Tail = list2
        list2 = list2.Next
    }
    count := 0
    list1Head := list1
    for list1 != nil {
        next := list1.Next
        if count == a - 1 {
            list1.Next = list2Head
        } else if count == b {
            list2Tail.Next = list1.Next
        }
        list1 = next
        count++
    }
    return list1Head
}

func leastInterval(tasks []byte, n int) int {
	if n == 0 {
		return len(tasks)
	}

	cnt := make([]int, 26)
	for _, task := range tasks {
		cnt[task - 'A']++
	}

	var maxCount, sameMaxCount int
	for _, c := range cnt {
		if c > maxCount {
			maxCount = c
			sameMaxCount = 1
		} else if c == maxCount {
			sameMaxCount++
		}
	}

	res := (n + 1) * (maxCount - 1) + sameMaxCount
    if (res > len(tasks)) {
        return res
    } else {
        return len(tasks)
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode {
    l := list1
    for i := 1; i <= a - 1; i++ {
        l = l.Next
    }

    prev := l
    r := l
    for i := a; i <= b + 1; i++ {
        r = r.Next
        prev.Next = nil
        prev = r
    }

    list2Tail := list2
    for list2Tail.Next != nil {
        list2Tail = list2Tail.Next
    }

    l.Next = list2
    list2Tail.Next = r

    return list1
}

func findMinArrowShots(points [][]int) int {
    // Sort the balloons based on their end coordinates
    sort.Slice(points, func(i, j int) bool {
        return points[i][1] < points[j][1]
    })

    arrows := 1
    prevEnd := points[0][1]

    // Count the number of non-overlapping intervals
    for i := 1; i < len(points); i++ {
        if points[i][0] > prevEnd {
            arrows++
            prevEnd = points[i][1]
        }
    }

    return arrows
}

func findMaxLength(nums []int) int {
    hashmap := make(map[int]int)
    zeros, ones, maxLen := 0, 0, 0
    hashmap[0] = -1 
    for i, num := range nums {
        if num == 0 {
            zeros++
        } else {
            ones++
        }
        diff := zeros - ones
        if val, ok := hashmap[diff]; ok {
            maxLen = max(maxLen, i - val)
        } else {
            hashmap[diff] = i
        }
    }
    return maxLen
}

func insert(intervals [][]int, newInterval []int) [][]int {
	var result [][]int

    // Iterate through intervals and add non-overlapping intervals before newInterval
	i := 0
	for i < len(intervals) && intervals[i][1] < newInterval[0] {
		result = append(result, intervals[i])
		i++
	}

    // Merge overlapping intervals
	for i < len(intervals) && intervals[i][0] <= newInterval[1] {
		newInterval[0] = int(math.Min(float64(newInterval[0]), float64(intervals[i][0])))
		newInterval[1] = int(math.Max(float64(newInterval[1]), float64(intervals[i][1])))
		i++
	}

    // Add merged newInterval
	result = append(result, newInterval)

    // Add non-overlapping intervals after newInterval
	for i < len(intervals) {
		result = append(result, intervals[i])
		i++
	}

	return result
}