# 기본
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
 
# Lower bound — target 이상인 첫 번째 인덱스
def lower_bound(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo
 
# Upper bound — target 초과인 첫 번째 인덱스
def upper_bound(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo
 
# Python 내장
import bisect
bisect.bisect_left(arr, target)   # lower bound
bisect.bisect_right(arr, target)  # upper bound

# 합이 target인 두 수 찾기
def two_sum(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)
        elif s < target:
            lo += 1
        else:
            hi -= 1
    return None

# 길이 k인 부분 배열의 최대 합
def max_sum_window(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum
 
# 합이 target 이상인 최소 길이 부분 배열
def min_length_subarray(arr, target):
    lo = total = 0
    result = float('inf')
    for hi in range(len(arr)):
        total += arr[hi]
        while total >= target:
            result = min(result, hi - lo + 1)
            total -= arr[lo]
            lo += 1
    return result if result != float('inf') else 0

# 거듭제곱 O(log n)
def power(base, exp):
    if exp == 0: return 1
    if exp % 2 == 0:
        half = power(base, exp // 2)
        return half * half
    return base * power(base, exp - 1)
 
# 최대 부분 배열 (카데인 변형)
def max_crossing_sum(arr, lo, mid, hi):
    left_sum = right_sum = float('-inf')
    total = 0
    for i in range(mid, lo-1, -1):
        total += arr[i]
        left_sum = max(left_sum, total)
    total = 0
    for i in range(mid+1, hi+1):
        total += arr[i]
        right_sum = max(right_sum, total)
    return left_sum + right_sum

# N-Queens
def solve_n_queens(n):
    result = []
    cols = set()
    diag1 = set()  # r - c
    diag2 = set()  # r + c
 
    def backtrack(row, path):
        if row == n:
            result.append(path[:])
            return
        for col in range(n):
            if col in cols or (row-col) in diag1 or (row+col) in diag2:
                continue
            cols.add(col); diag1.add(row-col); diag2.add(row+col)
            path.append(col)
            backtrack(row + 1, path)
            path.pop()
            cols.remove(col); diag1.remove(row-col); diag2.remove(row+col)
 
    backtrack(0, [])
    return result
 
# 순열
def permutations(nums):
    result = []
    def backtrack(path, used):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i, n in enumerate(nums):
            if used[i]: continue
            used[i] = True
            path.append(n)
            backtrack(path, used)
            path.pop()
            used[i] = False
    backtrack([], [False] * len(nums))
    return result