Problem:


Score : 100 points

Problem Statement

There are N slimes lining up in a row.
Initially, the i-th slime from the left has a size of a_i.

Taro is trying to combine all the slimes into a larger slime.
He will perform the following operation repeatedly until there is only one slime:

Choose two adjacent slimes, and combine them into a new slime. The new slime has a size of x + y, where x and y are the sizes of the slimes before combining them. Here, a cost of x + y is incurred. The positional relationship of the slimes does not change while combining slimes.

Find the minimum possible total cost incurred.

Constraints

All values in input are integers.

2 \leq N \leq 400

1 \leq a_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 \ldots a_N

Output

Print the minimum possible total cost incurred.

Sample Input 1

4
10 20 30 40

Sample Output 1

190

Taro should do as follows (slimes being combined are shown in bold):

(10, 20, 30, 40) → (30, 30, 40)

(30, 30, 40) → (60, 40)

(60, 40) → (100)

Sample Input 2

5
10 10 10 10 10

Sample Output 2

120

Taro should do, for example, as follows:

(10, 10, 10, 10, 10) → (20, 10, 10, 10)

(20, 10, 10, 10) → (20, 20, 10)

(20, 20, 10) → (20, 30)

(20, 30) → (50)

Sample Input 3

3
1000000000 1000000000 1000000000

Sample Output 3

5000000000

The answer may not fit into a 32-bit integer type.

Sample Input 4

6
7 6 8 6 1 1

Sample Output 4

68

Taro should do, for example, as follows:

(7, 6, 8, 6, 1, 1) → (7, 6, 8, 6, 2)

(7, 6, 8, 6, 2) → (7, 6, 8, 8)

(7, 6, 8, 8) → (13, 8, 8)

(13, 8, 8) → (13, 16)

(13, 16) → (29)



Sample input:
4
10 20 30 40


Sample output:
190

Submission status: Accepted

Solution code:
def main():
    import sys
    from itertools import accumulate
    input = sys.stdin.readline
    N = int(input())
    a = list(map(int, input().split()))
    inf = 10 ** 13
    dp = [[0]*N for i in range(N)]
    s = [0] + list(accumulate(a))
    for i, x in enumerate(a):
        dp[i][i] = 0
    for i in range(N-2, -1, -1):
        DP = dp[i]
        si = s[i]
        for j in range(i+1, N):
            tmp = s[j+1] - si
            D = inf
            for k in range(i, j):
                cost = DP[k]+dp[k+1][j]
                if D > cost:
                    D = cost
            DP[j] = D + tmp
    print(dp[0][N-1])


main()

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
A = [0] + list(map(int, input().split()))
S = np.cumsum(A, dtype=np.int64)

dp = np.zeros((N + 1, N + 1), dtype=np.int64)
for length in range(2, N + 1):
    for l in range(N - length + 1):
        r = length + l
        dp[l][r] = np.amin(dp[l, l + 1:r] + dp[l + 1:r, r]) + S[r] - S[l]
print(dp[0][N])

Submission status: Accepted

Solution code:
N=int(input())
A=[0]+list(map(int,input().split()))

#累積和
#C[index]=A[1]+...+A[index](1<=index<=N)
C=[0]*(N+1)
C[1]=A[1]
for index1 in range(2,N+1):
    C[index1]+=C[index1-1]+A[index1]

DP=[[0]*(N+1) for index2 in range(N+1)]


def mincost(i,j):   #i<=j
    global A
    global DP

    if DP[i][j]>0:
        return DP[i][j]
    if i==j:
        return DP[i][j]
    else:
        res=float('inf')
        sum=C[j]-C[i-1]
        for k in range(i,j):
            res=min(res,mincost(i,k)+mincost(k+1,j)+sum)
        DP[i][j]=res
        return DP[i][j]

mincost(1,N)
print(DP[1][N])

#for index3 in range(N+1):
    #string=''
    #for index4 in range(N+1):
        #string+=str(DP[index3][index4])+' '
    #print(string)

Submission status: Accepted

Solution code:
n = int(input())
*A, = map(int, input().split())
S = [0]
for i in range(n):
    S.append(S[-1]+A[i])
DP = [[None for j in range(n+1)] for i in range(n)]
def dp(i, j):
    if j <= i+1:
        return 0
    if DP[i][j] != None:
        return DP[i][j]
    DP[i][j] = S[j]-S[i]+min([dp(i, k)+dp(k, j) for k in range(i+1, j)])
    return DP[i][j]
print(dp(0, n))

Submission status: Accepted

Solution code:
n = int(input())
*A, = map(int, input().split())
S = [0]
for i in range(n):
    S.append(S[-1]+A[i])
DP = [[None for r in range(n+1)] for l in range(n)]
def dp(l, r):
    if r <= l+1:
        return 0
    if DP[l][r] != None:
        return DP[l][r]
    DP[l][r] = S[r]-S[l]+min([dp(l, i)+dp(i, r) for i in range(l+1, r)])
    return DP[l][r]
print(dp(0, n))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

from itertools import groupby, accumulate, product, permutations, combinations

def solve(N,A):
    dp = [[0]*N for _ in range(N)] #dp[i][j] i人目まででj個を分ける場合の数
    cum = [0]+list(accumulate(A))
    for k in range(1,N):
        for i in range(N-k):
            j = i + k
            dp[i][j] = cum[j+1]-cum[i] + min([dp[i][i+l]+dp[i+l+1][j] for l in range(k)])
    ans = dp[0][N-1]
    return ans
print(solve(N,A))

Submission status: Accepted

Solution code:
# dp[l][r]=min(区間[l,r]を合成するための最小コスト)
n=int(input())
a=list(map(int,input().split()))
INF=10**15
dp=[[0]*n for i in range(n)]
for i in range(n):
    dp[i][i]=a[i]
# 合成するときの必要経費を構成
for i in range(n-1):
    for j in range(i+1,n):
        dp[i][j]=dp[i][j-1]+a[j]
dp[0][-1]=0
# dp[i][j]=min(dp[i][k]+dp[k+1][j])+必要経費 で斜め(0,1),(1,2),(0,2),(1,3),...の順に見ていく
# ループの書き方に手間取った
for i in range(1,n):
    for j in range(n-i):
        ans=INF
        for k in range(j,i+j):
            ans=min(ans,dp[j][k]+dp[k+1][i+j])
        dp[j][i+j]+=ans
print(dp[0][-1])

Submission status: Accepted

Solution code:
# dp[l][r]=min(区間[l,r]を合成するための最小コスト)
n=int(input())
a=list(map(int,input().split()))
INF=10**15
dp=[[0]*n for i in range(n)]
for i in range(n):
    dp[i][i]=a[i]
# 合成するときの必要経費を構成
for i in range(n-1):
    for j in range(i+1,n):
        dp[i][j]=dp[i][j-1]+a[j]
dp[0][-1]=0
# dp[i][j]=min(dp[i][k]+dp[k+1][j])+必要経費 で斜め(0,1),(1,2),(0,2),(1,3),...の順に見ていく
# ループの書き方に手間取った
for i in range(n-1):
    for j in range(i+1,n):
        ans=INF
        x=j-i-1
        for k in range(x,j):
            ans=min(ans,dp[x][k]+dp[k+1][j])
        dp[x][j]+=ans
print(dp[0][-1])

Submission status: Accepted

Solution code:
n = int(input())
*A, = map(int, input().split())
# n = 4
# A = [10, 20, 30, 40]
DP = [[None for r in range(n+1)] for l in range(n)]
S = [0]
for i in range(n):
    S.append(S[-1]+A[i])


def dp(l, r):
    # 区間[l,r)での最小コスト
    if r <= l+1:
        DP[l][r] = 0
    if DP[l][r] != None:
        return DP[l][r]
    # S[r]-S[l]=sum(A[l:r])
    DP[l][r] = S[r]-S[l]+min([dp(l, i)+dp(i, r) for i in range(l+1, r)])
    return DP[l][r]


print(dp(0, n))

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
asum=[0 for i in range(0,N+1)]
for i in range(1,N+1):
    asum[i]=A[i-1]+asum[i-1]

dp=[[0 for i in range(0,N+1)] for j in range(0,N)]

for i in range(0,N):
    if N>i+1:
        dp[i][2]=A[i]+A[i+1]

for j in range(3,N+1):
    for i in range(0,N):
        if N>i+j-1 and j!=3:
            ans=min(A[i]+asum[i+j]-asum[i+1]+dp[i+1][j-1],asum[i+j-1]-asum[i]+dp[i][j-1]+A[i+j-1])
            test=min(dp[i][k]+dp[i+k][j-k]+asum[i+k]-asum[i]+asum[i+j]-asum[i+k] for k in range(2,j-1))
            dp[i][j]=min(ans,test)
        elif N>i+j-1:
            dp[i][j]=min(A[i]+asum[i+j]-asum[i+1]+dp[i+1][j-1],asum[i+j-1]-asum[i]+dp[i][j-1]+A[i+j-1])


print(dp[0][N])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines 
MOD = 10**9+7


def resolve():
    def dfs(l, r):
        if r - l == 1:
            dp[l][r] = A[l] + A[r]
            return dp[l][r]

        if dp[l][r] is not None:
            return dp[l][r]

        ret = 1<<60
        for x in range(l,r):
            cost = cum_A[r+1] - cum_A[l]
            ret = min(ret, dfs(l, x) + dfs(x+1, r) + cost)

        dp[l][r] = ret
        return ret

    N = int(input())
    A = list(map(int, input().split()))
    cum_A = [0]*(N+1)
    for i in range(N):
        cum_A[i+1] = cum_A[i] + A[i]

    dp = [[None]*(N+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][i] = 0

    return print(dfs(0, N-1))

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    cum_A = [0]*(N+1)
    for i in range(N):
        cum_A[i+1] = cum_A[i] + A[i]

    dp = [[1<<60]*(N+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][i] = 0

    for l in range(2, N+1):
        # right = left + len - 1でrightが[0, N - 1]のように
        for left in range(N-l+1):
            right = left + l-1
            #if right>= N: continue
            cost = cum_A[right+1] - cum_A[left]
            for k in range(left, right):
                tmp = dp[left][k] + dp[k+1][right] + cost
                dp[left][right] = min(dp[left][right], tmp)

    return print(dp[0][N-1])

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return tuple(map(int, input().split()))


def main():
    N = int(input())
    A = inpl()
    cumA = [0] * (N + 1)
    for i, a in enumerate(A):
        cumA[i + 1] = cumA[i] + a
    dp = [[float('inf')] * N for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0

    for L in range(1, N):
        for i in range(N - L):
            dp[i][i + L] = cumA[i + L + 1] - cumA[i] + min(dp[i][i + k] + dp[i + k + 1][i + L] for k in range(L))
        # print(dp)
    print(dp[0][N - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]

dp = [[10 ** 18] * n for _ in range(n)]
dp[0] = [0] * n

s = [0]
for i in a:
    s.append(s[-1]+i)


for i in range(1, n):
    for j in range(n):
        if i + j < n:
            b = 10 ** 18
            for k in range(i):
                l = i - k - 1
                b = min(b, dp[k][j]+dp[l][j+k+1])
            dp[i][j] = b + s[i+j+1]-s[j]

print(dp[-1][0])

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools

#input = sys.stdin.readline
def input():
    return sys.stdin.readline().strip("\n").strip(" ")

_NUMINT_ALL = list(range(10))
_START_TIME = time.time()
INDEX_KETA = 10**12
INF = 9223372036854775807

def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is None:
        return

    if isinstance(ans, tuple):
        split_print_space(ans)
    else:
        print(ans)


def solve():



    N = iip()
    A = iip()
    SA = [0]

    cur = 0
    for i in A:
        cur += i
        SA.append(cur)

    #print(SA)
    size = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(i, N):
            size[i][j] = int(SA[j+1]-SA[i])

    #fprint(size)

    dp = [[INF for _ in range(N)] for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0

    for d in range(N):
        for l in range(N):
            r = l+d
            if r >= N:
                continue

            if l==r:
                dp[l][r] = 0
            else:
                dp[l][r] = min(dp[l][r],
                               dp[l+1][r] + size[l][l] + size[l+1][r],
                               dp[l][r-1] + size[r][r] + size[l][r-1])

            for k in range(l, r):
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + size[l][k] + size[k+1][r])

    #fprint(dp)
    print(dp[0][-1])




#####################################################ライブラリ集ここから



def kiriage_warizan(a, b):
    return -(-a//b)

def iip(listed=False):  # 数字のinputをlistで受け取る
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    if isinstance(l, list):
        l = l[0] # 間違って要素１個のタプルを渡されても受け取る
    assert isinstance(l, int)
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def flatten(l):
    return list(itertools.chain.from_iterable(l))


def index_sorted(sorted_list, target):
    idx = bisect_left(sorted_list, target)
    if idx != len(sorted_list) and sorted_list[idx] == target:
        return idx
    else:
        return False


def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  # グラフ作成のための辺をリストで返す
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):                      # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    if isinstance(s, int):
        print(s)
        return
    keta = max([len(str(i)) for i in itertools.chain.from_iterable(s)])
    print("--------")
    for i in s:
        print([str(j).rjust(keta) for j in i])
    print("--------")


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  #  modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left", seido = 1): # 関数を二分探索
    l = left
    r = right
    if seido == 1:
        x = (l + r) // 2
    else:
        x = (l + r) / 2
    while r-l > seido:
        #print(x)
        if seido == 1:
            x = (l + r) // 2
        else:
            x = (l + r) / 2
        if func(x) == target:
            if side == "left":
                r=x
            else:
                l=x


        elif func(x) > target:
            r = x
        else:
            #print(r, l)
            l = x

    #print(l, r)
    if side == "left" and func(r) == target:
        return r
    elif side != "left" and func(l) == target:
        return l
    elif side == "left":
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  # リストを二分探索
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                #for i in path: # 経路圧縮
                #    self.parent[i] = cur
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools

#input = sys.stdin.readline
def input():
    return sys.stdin.readline().strip("\n").strip(" ")

_NUMINT_ALL = list(range(10))
_START_TIME = time.time()
INDEX_KETA = 10**12
INF = 18446744073709551615

def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is None:
        return

    if isinstance(ans, tuple):
        split_print_space(ans)
    else:
        print(ans)


def solve():



    N = iip()
    A = iip()
    SA = [0]

    cur = 0
    for i in A:
        cur += i
        SA.append(cur)

    #print(SA)
    size = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(i, N):
            size[i][j] = int(SA[j+1]-SA[i])

    #fprint(size)

    dp = [[INF for _ in range(N)] for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0

    for d in range(N):
        for l in range(N):
            r = l+d
            if r >= N:
                continue

            if l==r:
                dp[l][r] = 0
            else:
                dp[l][r] = min(dp[l][r],
                               dp[l+1][r] + size[l][l] + size[l+1][r],
                               dp[l][r-1] + size[r][r] + size[l][r-1])

            for k in range(l, r):
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + size[l][k] + size[k+1][r])

    #fprint(dp)
    print(dp[0][-1])




#####################################################ライブラリ集ここから



def kiriage_warizan(a, b):
    return -(-a//b)

def iip(listed=False):  # 数字のinputをlistで受け取る
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    if isinstance(l, list):
        l = l[0] # 間違って要素１個のタプルを渡されても受け取る
    assert isinstance(l, int)
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def flatten(l):
    return list(itertools.chain.from_iterable(l))


def index_sorted(sorted_list, target):
    idx = bisect_left(sorted_list, target)
    if idx != len(sorted_list) and sorted_list[idx] == target:
        return idx
    else:
        return False


def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  # グラフ作成のための辺をリストで返す
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):                      # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    if isinstance(s, int):
        print(s)
        return
    keta = max([len(str(i)) for i in itertools.chain.from_iterable(s)])
    print("--------")
    for i in s:
        print([str(j).rjust(keta) for j in i])
    print("--------")


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  #  modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left", seido = 1): # 関数を二分探索
    l = left
    r = right
    if seido == 1:
        x = (l + r) // 2
    else:
        x = (l + r) / 2
    while r-l > seido:
        #print(x)
        if seido == 1:
            x = (l + r) // 2
        else:
            x = (l + r) / 2
        if func(x) == target:
            if side == "left":
                r=x
            else:
                l=x


        elif func(x) > target:
            r = x
        else:
            #print(r, l)
            l = x

    #print(l, r)
    if side == "left" and func(r) == target:
        return r
    elif side != "left" and func(l) == target:
        return l
    elif side == "left":
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  # リストを二分探索
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                #for i in path: # 経路圧縮
                #    self.parent[i] = cur
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()