def main(): n = II() a = LI() #dp[+,-] dp = [[-inf,-inf] for i in range(n)] for i in range(n): dp[i][0] = -a[i] for i in range(1,n): dp[i][0] = max(dp[i-1][0],dp[i-1][1] - a[i]) dp[i][1] = max(dp[i-1][1],dp[i-1][0] + a[i]) # print(dp) print(max(dp[-1])) pass """==================fold line==================""" """import""" # array from bisect import bisect_left,bisect_right from heapq import heapify,heappop,heappush from collections import deque,defaultdict,Counter # math import math,random,cmath from math import comb,ceil,floor,factorial,gcd,lcm,atan2,sqrt,isqrt,pi,e from itertools import product,permutations,combinations,accumulate from functools import cmp_to_key, cache # system from typing import Generic, Iterable, Iterator, List, Tuple, TypeVar, Optional T = TypeVar('T') import sys sys.setrecursionlimit(10**9) """input""" #int-input def II() -> int : return int(input()) def MI() -> int : return map(int, input().split()) def TI() -> tuple[int] : return tuple(MI()) def LI() -> list[int] : return list(MI()) #str-input def SI() -> str : return input() def MSI() -> str : return input().split() def SI_L() -> list[str] : return list(SI()) def SI_LI() -> list[int] : return list(map(int, SI())) #multiple-input def LLI(n) -> list[list[int]]: return [LI() for _ in range(n)] def LSI(n) -> list[str]: return [SI() for _ in range(n)] #1-indexを0-indexでinput def MI_1() -> int : return map(lambda x:int(x)-1, input().split()) def TI_1() -> tuple[int] : return tuple(MI_1()) def LI_1() -> list[int] : return list(MI_1()) def ordalp(s:str) -> int|list[int]: if len(s) == 1: return ord(s)-ord("A") if s.isupper() else ord(s)-ord("a") return list(map(lambda i: ord(i)-ord("A") if i.isupper() else ord(i)-ord("a"), s)) def ordallalp(s:str) -> int|list[int]: if len(s) == 1: return ord(s)-ord("A")+26 if s.isupper() else ord(s)-ord("a") return list(map(lambda i: ord(i)-ord("A")+26 if i.isupper() else ord(i)-ord("a"), s)) def graph(n:str, m:str, dir:bool=False , index=-1) -> list[set[int]]: """ (頂点,辺,有向か,indexの調整) defaultは無向辺、(index)-1 """ edge = [set() for i in range(n+1+index)] for _ in range(m): a,b = map(int, input().split()) a,b = a+index,b+index edge[a].add(b) if not dir: edge[b].add(a) return edge def graph_w(n:str, m:str, dir:bool=False , index=-1) -> list[set[tuple]]: """ (頂点,辺,有向か,indexの調整) defaultは無向辺、index-1 """ edge = [set() for i in range(n+1+index)] for _ in range(m): a,b,c = map(int, input().split()) a,b = a+index,b+index edge[a].add((b,c)) if not dir: edge[b].add((a,c)) return edge """const""" mod, inf = 998244353, 1<<60 isnum = {int,float,complex} true, false, none = True, False, None def yes() -> None: print("Yes") def no() -> None: print("No") def yn(flag:bool) -> None: print("Yes" if flag else "No") def ta(flag:bool) -> None: print("Takahashi" if flag else "Aoki") alplow = "abcdefghijklmnopqrstuvwxyz" alpup = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" alpall = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" URDL = {'U':(-1,0), 'R':(0,1), 'D':(1,0), 'L':(0,-1)} DIR_4 = [[-1,0],[0,1],[1,0],[0,-1]] DIR_8 = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]] DIR_BISHOP = [[-1,1],[1,1],[1,-1],[-1,-1]] prime60 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59] # alias DD = defaultdict BSL = bisect_left BSR = bisect_right """math fanctions""" """point""" cross_pro = lambda p1,p2 : p2[0]*p1[1] - p2[1]*p1[0] #外積 dist = lambda p1,p2 : sqrt(pow(p1[0]-p2[0],2) + pow(p1[1]-p2[1],2)) def max_min_cross(p1, p2, p3, p4, touch = False): min_ab, max_ab = min(p1, p2), max(p1, p2) min_cd, max_cd = min(p3, p4), max(p3, p4) if touch: if min_ab > max_cd or max_ab < min_cd: return False return True else: if min_ab >= max_cd or max_ab <= min_cd: return False return True def cross_judge(a, b, c, d, touch = False): """線分abとcdの交差判定 接するも含むかどうか""" # x座標による判定 if not max_min_cross(a[0], b[0], c[0], d[0], touch): return False # y座標による判定 if not max_min_cross(a[1], b[1], c[1], d[1], touch): return False tc1 = (a[0] - b[0]) * (c[1] - a[1]) + (a[1] - b[1]) * (a[0] - c[0]) tc2 = (a[0] - b[0]) * (d[1] - a[1]) + (a[1] - b[1]) * (a[0] - d[0]) td1 = (c[0] - d[0]) * (a[1] - c[1]) + (c[1] - d[1]) * (c[0] - a[0]) td2 = (c[0] - d[0]) * (b[1] - c[1]) + (c[1] - d[1]) * (c[0] - b[0]) if touch: return tc1 * tc2 <= 0 and td1 * td2 <= 0 else: return tc1 * tc2 < 0 and td1 * td2 < 0 """primary function""" def prod(lst:list[int|str], mod = None) -> int|str: """product 文字列の場合連結""" ans = 1 if type(lst[0]) in isnum: for i in lst: ans *= i if mod: ans %= mod return ans else: return "".join(lst) def sigma(first:int, diff:int, term:int) -> int: #等差数列の和 return term*(first*2+(term-1)*diff)//2 def xgcd(a:int, b:int) -> tuple[int,int,int]: #Euclid互除法 """ans = a*x0 + b*y0""" x0, y0, x1, y1 = 1, 0, 0, 1 while b != 0: q, a, b = a // b, b, a % b x0, x1 = x1, x0 - q * x1 y0, y1 = y1, y0 - q * y1 return a, x0, y0 def modinv(a:int, mod = mod) -> int: #逆元 """逆元""" g, x, y = xgcd(a, mod) #g != 1は逆元が存在しない return -1 if g != 1 else x % m def nth_root(x:int, n:int, is_x_within_64bit = True) -> int: #n乗根 """floor(n√x)""" ngs = [-1, -1, 4294967296, 2642246, 65536, 7132, 1626, 566, 256, 139, 85, 57, 41, 31, 24, 20, 16, 14, 12, 11, 10, 9, 8, 7, 7, 6, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3] if x <= 1 or n == 1: return x if is_x_within_64bit: if n >= 64: return 1 ng = ngs[n] else: ng = x ok = 0 while abs(ok - ng) > 1: mid = (ok + ng)//2 if mid**n <= x: ok = mid else: ng = mid return ok def pi_base(p:list) -> Iterator: l = len(p) num = [0]*l while True: yield num num[~0] += 1 for i in range(l): if num[~i] == p[~i]: if i == l-1: return num[~i] = 0 num[~(i+1)] += 1 else: break """prime""" def primefact(n:int) -> dict[int,int]: #素因数分解 """素因数分解""" i = 2 pdict = dict() while i*i <= n: if n%i == 0: cnt = 0 while n%i == 0: n //= i cnt += 1 pdict[i] = cnt i += 1 if n != 1: pdict[n] = 1 return pdict def primenumber(lim:int, get = None) -> list[int]: #素数列挙 """ 素数列挙 sieve(n)もあります get == None : リスト get >= 1 : flag get < 1 : 累積和 """ lim += 1 #素数にはflagを立てる p = [1]*lim #それ以下の素数の数を保管 cntp = [0]*lim #素数列を格納 plist = [] p[0],p[1] = 0,0 for i in range(2,lim): if p[i]: plist.append(i) for j in range(2*i,lim,i): p[j] = 0 for i in range(1,lim): cntp[i] = cntp[i-1] + p[i] if get is None: return plist elif get >= 1: return p else: return cntp def divisors(n:int) -> list[int] : #約数列挙 """約数列挙""" divs_small, divs_big = [], [] i = 1 while i * i <= n: if n % i == 0: divs_small.append(i) divs_big.append(n // i) i += 1 if divs_big[-1] == divs_small[-1]: divs_big.pop() for e in reversed(divs_big): divs_small.append(e) return divs_small """binary number""" lenbit = lambda bit: (bit).bit_length() def popcnt(n:int) -> int: #popcnt """int.bit_count() があります 64bitまで""" c=(n&0x5555555555555555)+((n>>1)&0x5555555555555555) c=(c&0x3333333333333333)+((c>>2)&0x3333333333333333) c=(c&0x0f0f0f0f0f0f0f0f)+((c>>4)&0x0f0f0f0f0f0f0f0f) c=(c&0x00ff00ff00ff00ff)+((c>>8)&0x00ff00ff00ff00ff) c=(c&0x0000ffff0000ffff)+((c>>16)&0x0000ffff0000ffff) c=(c&0x00000000ffffffff)+((c>>32)&0x00000000ffffffff) return c def binchange(n:int,fill0 = None) -> str: """10進数(int)→2進数(str) fill0:0埋め桁数""" return format(n, "0"+str(fill0)+"b") if fill0 else format(n,"b") """list""" def prefix_op(lst:list, op = lambda x,y:x+y, e = 0) -> list: #累積和 """defaultは累積和""" n = len(lst) res = [e]*(n+1) for i in range(n): res[i+1] = op(res[i], lst[i]) return res def suffix_op(lst:list, op = lambda x,y:x+y, e = 0) -> list: #累積和 """defaultは累積和""" n = len(lst) res = [e]*(n+1) for i in reversed(range(n)): res[i] = op(res[i+1], lst[i]) return res def mex(lst:list) -> int: """補集合の最小非負整数""" l = set(lst) ans = 0 while ans in l: ans += 1 return ans def inversion_cnt(lst:list, flag = None) -> int: #転倒数 """転倒数 not順列→flag立てる""" n = len(lst) if not flag is None: comp = Compress(lst) lst = comp.comp else: lst = list(map(lambda x : x-1, lst)) ft = FenwickTree(n) ans = [0]*n #i要素目の転倒への寄与 for i in range(n): ans[i] = ft.sum(lst[i]+1,n) ft.add(lst[i], 1) return ans def doubling(nex:list, k:int = None ,a:list = None) -> list: """nex:操作列 k:回数 a:初期列""" n = len(nex) if k is None: log = 60 else: log = (k+1).bit_length() res = [[-1]*n for _ in range(log)] #ダブリング配列 res[0] = nex[:] for cnt in range(1,log): for i in range(n): tmp = res[cnt-1][i] res[cnt][i] = res[cnt-1][tmp] if k is None: return res ans = (nex[:] if a is None else a[:]) for cnt in range(log): if k & (1< int: """ 順列(同じ要素がない)が前提 最小操作回数を返す """ if sorted(a) != sorted(b): return -1 t = dict() cnt = 0 for i in range(n): x,y = a[i],b[i] if x == y: continue if x in t: while x in t: x_ = t[x] del t[x] x = x_ cnt += 1 if x == y: break else: t[y] = x else: t[y] = x return cnt """matrix""" def mul_matrix(A, B, mod = mod): #行列の積 A*B N = len(A) K = len(A[0]) M = len(B[0]) res = [[0 for _ in range(M)] for _ in range(N)] for i in range(N) : for j in range(K) : for k in range(M) : res[i][k] += A[i][j] * B[j][k] res[i][k] %= mod return res def pow_matrix(mat, exp, mod = mod): #二分累乗 N = len(mat) res = [[1 if i == j else 0 for i in range(N)] for j in range(N)] while exp > 0 : if exp%2 == 1 : res = mul_matrix(res, mat, mod) mat = mul_matrix(mat, mat, mod) exp //= 2 return res """enumerate""" def fact_enu(lim): #階乗列挙 #階乗 fac = [1] #階乗の逆数 divfac = [1] factorial = 1 for i in range(1,lim+1): factorial *= i factorial %= mod fac.append(factorial) divfac.append(pow(factorial,-1,mod)) return fac,divfac class Comb_enu: #combination列挙 def __init__(self,lim,mod = mod): """ mod : prime指定 lim以下のmodでcomdination計算 """ self.fac = [1,1] self.inv = [1,1] self.finv = [1,1] self.mod = mod for i in range(2,lim+1): self.fac.append(self.fac[i-1]*i%mod) self.inv.append(-self.inv[mod%i]*(mod//i)%mod) self.finv.append(self.finv[i-1]*self.inv[i]%mod) def comb(self,a,b): if a < b: return 0 if a < 0: return 0 return self.fac[a]*self.finv[b]*self.finv[a-b]%self.mod """str""" def int_0(str,l,r = None, over_ok = False): #str→int """ strの[l,r)桁をintで返す(0-index) 取れない場合はNone over_okを立てればrが桁を超えても返す """ lstr = len(str) if l > len(str): return None l = lstr - l if r == None: if "" == str[r:l]: return 0 return int(str[:l]) if r > len(str): if over_ok: return int(str[:l]) else: return None r = lstr - r if "" == str[r:l]: return 0 return int(str[r:l]) def lis(l): #後でちゃんと書き直してね # STEP1: LIS長パート with 使用位置 n = len(l) lisDP = [inf] * n # いまi文字目に使っている文字 indexList = [None] * n # lの[i]文字目が使われた場所を記録する for i in range(n): # 通常のLISを求め、indexListに使った場所を記録する ind = bisect_left(lisDP, l[i]) lisDP[ind] = l[i] indexList[i] = ind # STEP2: LIS復元パート by 元配列の使用した位置 # 後ろから見ていくので、まずは、LIS長目(targetIndex)のindexListを探したいとする targetIndex = max(indexList) ans = [0] * (targetIndex + 1) # 復元結果(indexListは0-indexedなのでlen=4ならmax=3で格納されているので+1する) # 後ろから見ていく for i in range(n - 1, -1, -1): # もし、一番最後に出てきているtargetIndexなら if indexList[i] == targetIndex: ans[targetIndex] = l[i] # ansのtargetIndexを確定 targetIndex -= 1 return ans """table operation""" def acc_sum(lst:list, dim = 2) -> list: if dim == 2: h,w = len(lst),len(lst[0]) res = [[0]*(w+1)] for i in range(h): res.append([0]) for j in range(w): res[-1].append(res[i+1][j] + lst[i][j]) for j in range(w): for i in range(h): res[i+1][j+1] += res[i][j+1] return res elif dim == 3: d1,d2,d3 = len(lst),len(lst[0]),len(lst[0][0]) res = [[[0]*(d3+1) for i in range(d2+1)]] for i in range(d1): res.append([[0]*(d3+1)]) for j in range(d2): res[-1].append([0]) for k in range(d3): res[-1][-1].append(res[i+1][j+1][k] + lst[i][j][k]) for j in range(d2): for k in range(d3): for i in range(d1): res[i+1][j+1][k+1] += res[i][j+1][k+1] for k in range(d3): for i in range(d1): for j in range(d2): res[i+1][j+1][k+1] += res[i+1][j][k+1] return res def copy_table(table): H,W = len(table), len(table[0]) res = [] for i in range(H): res.append([]) for j in range(W): res[-1].append(table[i][j]) return res def rotate_table(table): #反時計回りに回転 return list(map(list, zip(*table)))[::-1] def transpose_table(l): #行と列を入れ替え return [list(x) for x in zip(*l)] def bitconvert_table(table, letter1="#", rev=False): #各行bitに変換 H,W = len(table), len(table[0]) res = [] for h in range(H): rowBit = 0 for w in range(W): if rev: if table[h][w] == letter1: rowBit += 1< 0 or (y == 0 and x >= 0): yposi.append([x,y]) else: ynega.append([x,y]) yposi.sort(key = cmp_to_key(cross_pro)) ynega.sort(key = cmp_to_key(cross_pro)) return yposi+ynega def quick_sort(lst, comparision, left = 0, right = -1): """ (list,比較関数,(l),(r)) input : (p,q) output : True (p= j: break lst[i],lst[j] = lst[j],lst[i] i += 1 j -= 1 if left < i - 1: quick_sort(lst, left, i - 1) if right > j + 1: quick_sort(lst, j + 1, right) def bubble_sort(lst): """返り値:転倒数""" cnt = 0 n = len(lst) for i in range(n): for j in reversed(range(i+1),n): if a[j] > a[j-1]: a[j],a[j-1] = a[j-1],a[j] cnt += 1 return cnt def topological_sort(egde, inedge=None): n = len(edge) if inedge == None: inedge = [0]*n for v in range(n): for adj in edge(v): inedge[adj] += 1 ans = [i for i in range(n) if inedge[i] == 0] que = deque(ans) while que: q = que.popleft() for e in edge[q]: inedge[e] -= 1 if inedge[e] == 0: que.append(e) ans.append(e) return ans """graph fanctions""" def dijkstra(edge, start=0, goal=None): """計算量 O((node+edge)log(edge))""" n = len(edge) dis = [inf]*n dis[start] = 0 que = [(0, start)] heapify(que) while que: cur_dis,cur_node = heappop(que) if dis[cur_node] < cur_dis: continue for next_node, weight in edge[cur_node]: next_dis = cur_dis + weight if next_dis < dis[next_node]: dis[next_node] = next_dis heappush(que, (next_dis, next_node)) if goal != None: return dis[goal] return dis def warshallfloyd(dis): n = len(dis) for i in range(n): dis[i][i] = 0 for k in range(n): for i in range(n): for j in range(n): dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]) return dis def bellmanford(edge, start=0, goal=None): """ 始点と終点が決まっている 始点から到達可能かつ、終点に到達可能な閉路のみ検出 """ n = len(edge) dis = [inf]*n pre = [-1]*n #最短経路における直前にいた頂点 negative = [False]*n #たどり着くときに負の閉路があるかどうか dis[start] = 0 for t in range(2*n): for u in range(n): for v, cost in edge[u]: if dis[v] > dis[u] + cost: if t >= n-1 and v == goal: return None #0と衝突しないように elif i >= n-1: dis[v] = -inf else: dis[v] = dis[u] + cost pre[v] = u return dis[goal] #通常はここで終わり #最短経路の復元 x = goal path = [x] while x != start: x = pre[x] path.append(x) #最短経路を含む負の閉路があるかどうか for i in reversed(range(len(path)-1)): u, v = path[i+1], path[i] if dis[v] > dis[u] + cost: dis[v] = dis[u] + cost negative[v] = True if negative[u]: negative[v] = True if negative[end]: return -1 else: return d[end] #ループ検出書くの嫌いなので用意しましょう def loop(g): pass """data stucture""" #双方向リスト # https://github.com/tatyam-prime/SortedSet?tab=readme-ov-file class SortedSet(Generic[T]): BUCKET_RATIO = 16 SPLIT_RATIO = 24 def __init__(self, a: Iterable[T] = []) -> None: "Make a new SortedSet from iterable. / O(N) if sorted and unique / O(N log N)" a = list(a) n = len(a) if any(a[i] > a[i + 1] for i in range(n - 1)): a.sort() if any(a[i] >= a[i + 1] for i in range(n - 1)): a, b = [], a for x in b: if not a or a[-1] != x: a.append(x) n = self.size = len(a) num_bucket = int(math.ceil(math.sqrt(n / self.BUCKET_RATIO))) self.a = [a[n * i // num_bucket : n * (i + 1) // num_bucket] for i in range(num_bucket)] def __iter__(self) -> Iterator[T]: for i in self.a: for j in i: yield j def __reversed__(self) -> Iterator[T]: for i in reversed(self.a): for j in reversed(i): yield j def __eq__(self, other) -> bool: return list(self) == list(other) def __len__(self) -> int: return self.size def __repr__(self) -> str: return "SortedSet" + str(self.a) def __str__(self) -> str: s = str(list(self)) return "{" + s[1 : len(s) - 1] + "}" def _position(self, x: T) -> Tuple[List[T], int, int]: "return the bucket, index of the bucket and position in which x should be. self must not be empty." for i, a in enumerate(self.a): if x <= a[-1]: break return (a, i, bisect_left(a, x)) def __contains__(self, x: T) -> bool: if self.size == 0: return False a, _, i = self._position(x) return i != len(a) and a[i] == x def add(self, x: T) -> bool: "Add an element and return True if added. / O(√N)" if self.size == 0: self.a = [[x]] self.size = 1 return True a, b, i = self._position(x) if i != len(a) and a[i] == x: return False a.insert(i, x) self.size += 1 if len(a) > len(self.a) * self.SPLIT_RATIO: mid = len(a) >> 1 self.a[b:b+1] = [a[:mid], a[mid:]] return True def _pop(self, a: List[T], b: int, i: int) -> T: ans = a.pop(i) self.size -= 1 if not a: del self.a[b] return ans def discard(self, x: T) -> bool: "Remove an element and return True if removed. / O(√N)" if self.size == 0: return False a, b, i = self._position(x) if i == len(a) or a[i] != x: return False self._pop(a, b, i) return True def lt(self, x: T) -> Optional[T]: "Find the largest element < x, or None if it doesn't exist." for a in reversed(self.a): if a[0] < x: return a[bisect_left(a, x) - 1] def le(self, x: T) -> Optional[T]: "Find the largest element <= x, or None if it doesn't exist." for a in reversed(self.a): if a[0] <= x: return a[bisect_right(a, x) - 1] def gt(self, x: T) -> Optional[T]: "Find the smallest element > x, or None if it doesn't exist." for a in self.a: if a[-1] > x: return a[bisect_right(a, x)] def ge(self, x: T) -> Optional[T]: "Find the smallest element >= x, or None if it doesn't exist." for a in self.a: if a[-1] >= x: return a[bisect_left(a, x)] def __getitem__(self, i: int) -> T: "Return the i-th element." if i < 0: for a in reversed(self.a): i += len(a) if i >= 0: return a[i] else: for a in self.a: if i < len(a): return a[i] i -= len(a) raise IndexError def pop(self, i: int = -1) -> T: "Pop and return the i-th element." if i < 0: for b, a in enumerate(reversed(self.a)): i += len(a) if i >= 0: return self._pop(a, ~b, i) else: for b, a in enumerate(self.a): if i < len(a): return self._pop(a, b, i) i -= len(a) raise IndexError def index(self, x: T) -> int: "Count the number of elements < x." ans = 0 for a in self.a: if a[-1] >= x: return ans + bisect_left(a, x) ans += len(a) return ans def index_right(self, x: T) -> int: "Count the number of elements <= x." ans = 0 for a in self.a: if a[-1] > x: return ans + bisect_right(a, x) ans += len(a) return ans class SortedList(Generic[T]): BUCKET_RATIO = 16 SPLIT_RATIO = 24 def __init__(self, a: Iterable[T] = []) -> None: "Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)" a = list(a) n = self.size = len(a) if any(a[i] > a[i + 1] for i in range(n - 1)): a.sort() num_bucket = int(math.ceil(math.sqrt(n / self.BUCKET_RATIO))) self.a = [a[n * i // num_bucket : n * (i + 1) // num_bucket] for i in range(num_bucket)] def __iter__(self) -> Iterator[T]: for i in self.a: for j in i: yield j def __reversed__(self) -> Iterator[T]: for i in reversed(self.a): for j in reversed(i): yield j def __eq__(self, other) -> bool: return list(self) == list(other) def __len__(self) -> int: return self.size def __repr__(self) -> str: return "SortedMultiset" + str(self.a) def __str__(self) -> str: s = str(list(self)) return "{" + s[1 : len(s) - 1] + "}" def _position(self, x: T) -> Tuple[List[T], int, int]: "return the bucket, index of the bucket and position in which x should be. self must not be empty." for i, a in enumerate(self.a): if x <= a[-1]: break return (a, i, bisect_left(a, x)) def __contains__(self, x: T) -> bool: if self.size == 0: return False a, _, i = self._position(x) return i != len(a) and a[i] == x def count(self, x: T) -> int: "Count the number of x." return self.index_right(x) - self.index(x) def add(self, x: T) -> None: "Add an element. / O(√N)" if self.size == 0: self.a = [[x]] self.size = 1 return a, b, i = self._position(x) a.insert(i, x) self.size += 1 if len(a) > len(self.a) * self.SPLIT_RATIO: mid = len(a) >> 1 self.a[b:b+1] = [a[:mid], a[mid:]] def _pop(self, a: List[T], b: int, i: int) -> T: ans = a.pop(i) self.size -= 1 if not a: del self.a[b] return ans def discard(self, x: T) -> bool: "Remove an element and return True if removed. / O(√N)" if self.size == 0: return False a, b, i = self._position(x) if i == len(a) or a[i] != x: return False self._pop(a, b, i) return True def lt(self, x: T) -> Optional[T]: "Find the largest element < x, or None if it doesn't exist." for a in reversed(self.a): if a[0] < x: return a[bisect_left(a, x) - 1] def le(self, x: T) -> Optional[T]: "Find the largest element <= x, or None if it doesn't exist." for a in reversed(self.a): if a[0] <= x: return a[bisect_right(a, x) - 1] def gt(self, x: T) -> Optional[T]: "Find the smallest element > x, or None if it doesn't exist." for a in self.a: if a[-1] > x: return a[bisect_right(a, x)] def ge(self, x: T) -> Optional[T]: "Find the smallest element >= x, or None if it doesn't exist." for a in self.a: if a[-1] >= x: return a[bisect_left(a, x)] def __getitem__(self, i: int) -> T: "Return the i-th element." if i < 0: for a in reversed(self.a): i += len(a) if i >= 0: return a[i] else: for a in self.a: if i < len(a): return a[i] i -= len(a) raise IndexError def pop(self, i: int = -1) -> T: "Pop and return the i-th element." if i < 0: for b, a in enumerate(reversed(self.a)): i += len(a) if i >= 0: return self._pop(a, ~b, i) else: for b, a in enumerate(self.a): if i < len(a): return self._pop(a, b, i) i -= len(a) raise IndexError def index(self, x: T) -> int: "Count the number of elements < x." ans = 0 for a in self.a: if a[-1] >= x: return ans + bisect_left(a, x) ans += len(a) return ans def index_right(self, x: T) -> int: "Count the number of elements <= x." ans = 0 for a in self.a: if a[-1] > x: return ans + bisect_right(a, x) ans += len(a) return ans class Deque: #両端以外もO(1)でアクセスできるdeque def __init__(self, src_arr=[], max_size=300000): self.N = max(max_size, len(src_arr)) + 1 self.buf = list(src_arr) + [None] * (self.N - len(src_arr)) self.head = 0 self.tail = len(src_arr) def __index(self, i): l = len(self) if not -l <= i < l: raise IndexError('index out of range: ' + str(i)) if i < 0: i += l return (self.head + i) % self.N def __extend(self): ex = self.N - 1 self.buf[self.tail+1 : self.tail+1] = [None] * ex self.N = len(self.buf) if self.head > 0: self.head += ex def is_full(self): return len(self) >= self.N - 1 def is_empty(self): return len(self) == 0 def append(self, x): if self.is_full(): self.__extend() self.buf[self.tail] = x self.tail += 1 self.tail %= self.N def appendleft(self, x): if self.is_full(): self.__extend() self.buf[(self.head - 1) % self.N] = x self.head -= 1 self.head %= self.N def pop(self): if self.is_empty(): raise IndexError('pop() when buffer is empty') ret = self.buf[(self.tail - 1) % self.N] self.tail -= 1 self.tail %= self.N return ret def popleft(self): if self.is_empty(): raise IndexError('popleft() when buffer is empty') ret = self.buf[self.head] self.head += 1 self.head %= self.N return ret def __len__(self): return (self.tail - self.head) % self.N def __getitem__(self, key): return self.buf[self.__index(key)] def __setitem__(self, key, value): self.buf[self.__index(key)] = value def __str__(self): return 'Deque({0})'.format(str(list(self))) class WeightedUnionFind: #重み付きunion-find def __init__(self, N): self.N = N self.parents = [-1] * N self.rank = [0] * N self.weight = [0] * N def root(self, x): if self.parents[x] == -1: return x rx = self.root(self.parents[x]) self.weight[x] += self.weight[self.parents[x]] self.parents[x] = rx return self.parents[x] def get_weight(self, x): self.root(x) return self.weight[x] def unite(self, x, y, d): ''' A[x] - A[y] = d ''' w = d + self.get_weight(x) - self.get_weight(y) rx = self.root(x) ry = self.root(y) if rx == ry: _, d_xy = self.diff(x, y) if d_xy == d: return True else: return False if self.rank[rx] < self.rank[ry]: rx, ry = ry, rx w = -w if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1 self.parents[ry] = rx self.weight[ry] = w return True def is_same(self, x, y): return self.root(x) == self.root(y) def diff(self, x, y): if self.is_same(x, y): return True, self.get_weight(y) - self.get_weight(x) else: return False, 0 """binary search""" def bi_int(comparison, ok = 0, ng = inf): """ [lowlim,ans)だとTrueで[ans,uplim)だとFalse のイメージで実装 """ if not pred(ok): #条件を満たすことがない return ok while abs(ng - ok) > 1: mid = ok + (ng - ok)//2 if comparison(mid): ok = mid else: ng = mid return ok def bi_float(comparison, ok = 0, ng = inf, error = 10**(-9)): """ [lowlim,ans)だとTrueで[ans,uplim)だとFalse のイメージで実装 """ if not pred(ok): #条件を満たすことがない return ok #相対誤差と絶対誤差のどちらかがerror以下で終了 while abs(ng - ok)/abs(ng) > error and abs(ng - ok) > eroor: mid = ok + (ng - ok)/2 if comparison(mid): ok = mid else: ng = mid return ok """compress""" class Compress: #座標圧縮(一次元) def __init__(self, arr): values = sorted(set(arr)) self.translator = dict([(values[i], i) for i in range(len(values))]) self.inv_translator = values self.comp = [] for x in arr: self.comp.append(self.translator[x]) #圧縮前→圧縮後 def to_comp(self, x): return self.translator[x] #圧縮後→圧縮前 def from_comp(self, v): return self.inv_translator[v] #lstを変換 def lst_comp(self, lst): return [self.to_comp(i) for i in lst] class Compress2D: #2次元リスト[x,y]の座標圧縮 def __init__(self, arr): self.x = Compress([x for x, y in arr]) self.y = Compress([y for x, y in arr]) self.comp = [] for x,y in arr: self.comp.append([self.x.translator[x],self.y.translator[y]]) #圧縮前→圧縮後 def to_comp(self, x): return (self.x.translator[x[0]], self.y.translator[x[1]]) #圧縮後→圧縮前 def from_comp(self, v): return (self.x.translator[v[0]], self.y.translator[v[1]]) class RollingHash: #hash化 def __init__(self, string, base = 37, mod = 10**9 + 9): self.mod = mod l = len(string) self.hash = [0]*(l+1) for i in range(1,l+1): self.hash[i] = ( self.hash[i-1] * base + ord(string[i-1]) ) % mod self.pw = [1]*(l+1) for i in range(1,l+1): self.pw[i] = self.pw[i-1] * base % mod def get(self, l, r): """s[l:r]のhash""" return (self.hash[r] - self.hash[l] * self.pw[r-l]) % self.mod class ZobristHash: #多重集合の一致判定 def __init__(self, n, as_list:bool = False, mod = (1<<61)-1): self.N = n self.conversion = [random.randint(1, mod - 1) for i in range(n+1)] self.as_list = as_list #setとして扱うかlistの並び替えか self.Mod = mod def makehash(self, a:list): la = len(a) hashlst = [0]*(la+1) if self.as_list: #listの並び替えとしての一致 for i in range(la): hashlst[i+1] = (hashlst[i]+self.conversion[a[i]])%self.Mod return hashlst else: #setとしての一致 cnt = {} for i in range(la): if a[i] in cnt: hashlst[i+1] = hashlst[i+1] continue cnt.add(a[i]) hashlst[i+1] = hashlst[i]^self.conversion[a[i]] return hashlst def get(self, hashedlst:list, l:int, r:int): """a[l:r]のhashを返します""" if self.as_list: return (hashedlst[r]-hashedlst[l])%self.Mod else: return hashedlst[r]^hashedlst[l] """畳み込み??""" """graph""" class GridSearch: def __init__(self, table): """盤面の受取""" self.table = table self.H = len(table) self.W = len(table[0]) self.wall = "#" self.dist = [[inf]*self.W for _ in range(self.H)] def find(self, c): """始点,終点等の取得""" for h in range(self.H): for w in range(self.W): if self.table[h][w] == c: return (h,w) return None def set_wall(self, string): """壁の設定""" self.wall = string def can_start(self, *start): """探索済みでないかつ壁でない""" if len(start) == 1: i,j = start[0][0],start[0][1] else: i,j = start[0],start[1] if self.dist[i][j] == inf and not self.table[i][j] in self.wall: return True else: return False def island(self, transition = DIR_4): """連結成分の検出""" H, W = self.H, self.W self.island_id = [[-1]*W for _ in range(H)] self.island_size = [[-1]*W for _ in range(H)] crr_id = 0 id2size = dict() for sh in range(H): for sw in range(W): if self.table[sh][sw] in self.wall: continue if self.island_id[sh][sw] != -1: continue deq = deque() deq.append((sh,sw)) crr_size = 1 self.island_id[sh][sw] = crr_id while deq: h,w = deq.popleft() for dh, dw in transition: nh, nw = h+dh, w+dw if (not 0<= nh < H) or (not 0 <= nw < W): continue if self.table[nh][nw] in self.wall: continue if self.island_id[nh][nw] == -1: self.island_id[nh][nw] = crr_id deq.append((nh, nw)) crr_size += 1 id2size[crr_id] = crr_size crr_id += 1 for h in range(H): for w in range(W): if self.table[h][w] in self.wall: continue self.island_size[h][w] = id2size[self.island_id[h][w]] return self.island_id, self.island_size def DFS(self, start, goal=None, transition = DIR_4): """ DFSをします input : (start,(goal),(transition)) output : dis(table) or goalまでのdis(int) """ H, W = self.H, self.W deq = deque() deq.append(start) self.dist[start[0]][start[1]] = 0 if start == goal: return 0 while deq: h,w = deq.popleft() for dh, dw in transition: nh = h+dh nw = w+dw # gridの範囲外. if (not 0 <= nh < H) or (not 0 <= nw < W): continue # wallに設定されている文字なら. if self.table[nh][nw] in self.wall: continue new_dist = self.dist[h][w] + 1 #goalが引数で与えられていてgoalに達したら終了. if goal and (nh,nw) == goal: return new_dist if self.dist[nh][nw] > new_dist: self.dist[nh][nw] = new_dist deq.append((nh,nw)) if goal: return -1 return self.dist def DFS_break(self, start, goal=None, transition = DIR_4): """ 壁をcost = 1で破壊できる それ以外の移動はcost = 0 input : (start,(goal),(transition)) output : dis(table) or goalまでのdis(int) """ H, W = self.H, self.W deq = deque() deq.append(start) self.dist[start[0]][start[1]] = 0 if start == goal: return 0 while deq: h,w = deq.popleft() for dh, dw in transition: nh = h+dh nw = w+dw # gridの範囲外. if (not 0 <= nh < H) or (not 0 <= nw < W): continue now_dist = self.dist[h][w] #goalが引数で与えられていてgoalに達したら終了. if goal and (nh,nw) == goal: return now_dist # wallに設定されている文字なら. if self.table[nh][nw] in self.wall: if self.dist[nh][nw] > now_dist+1: self.dist[nh][nw] = now_dist+1 deq.append((nh,nw)) elif self.dist[nh][nw] > now_dist: self.dist[nh][nw] = now_dist deq.appendleft((nh,nw)) if goal: return -1 return self.dist #バリエーションとして #方向変換したら距離加算 #壁破壊で距離加算 #壁の種類として他のものがある #視線が壁になる #マグネット #移動に制限がある(エネルギー) class RootedTree: """ __allmethod__ autobuild -> obj : inputから構築 set_root -> None is_root,is_leaf -> bool yield_edges -> Iterator ### set_weight -> None : weightのdict生成 get_weight -> int : dictから重さを取得 get_depth -> int : rootからの深さ ### build_depth -> None : 深さの構築 build_des_size -> None : centroid_decomposition : build_centroid_dist is_member_of_centroid_tree is_id_larger get_higher_centroids_with_self yield_centroid_children find_lowest_common_centroid """ @classmethod def autobuild(cls, N, root = 0, input_index = 1): """ (u,v) , (u,v,c)に対応 rootを設定したくないならNone """ G = [[] for _ in range(N)] if N == 1: obj = RootedTree(G) if root is not None: obj.set_root(0) return obj line1 = list(map(int, input().split())) assert 2 <= len(line1) <= 3 # 重み無し. if len(line1) == 2: u,v = line1 u,v = u-input_index, v-input_index G[u].append(v) G[v].append(u) for _ in range(N-2): u,v = map(int, input().split()) u,v = u-input_index, v-input_index G[u].append(v) G[v].append(u) obj = RootedTree(G) if root is not None: obj.set_root(0) return obj else: u,v,c = line1 u,v = u-input_index, v-input_index G[u].append(v) G[v].append(u) edge = [(u,v,c)] for _ in range(N-2): u,v,c = map(int, input().split()) u,v = u-input_index, v-input_index G[u].append(v) G[v].append(u) edge.append((u,v,c)) obj = RootedTree(G) obj.set_weight(edge) if root is not None: obj.set_root(0) return obj def __init__(self, G): self.N = len(G) self.G = G self._rooted = False self._has_weight = False self._key = 10**7 def set_root(self, root): """ DFSついでにトポロジカルソート列も求める """ assert self._rooted == False self.root = root n, G = self.N, self.G par, ch, ts = [-1]*n, [[] for _ in range(n)], [] deq = deque([root]) while deq: v = deq.popleft() ts.append(v) for adj in G[v]: if adj == par[v]: continue par[adj] = v ch[v].append(adj) deq.append(adj) self.parent, self.children, self.ts_order = par, ch, ts self._rooted = True def encode(self, u, v): #edgte -> int return u*self._key + v def decode(self, uv): #int -> edge return divmod(uv, self._key) def is_root(self, v) -> bool: return v == self.root def is_leaf(self, v) -> bool: return len(self.children[v]) == 0 def yield_edges(self) -> Iterator[tuple]: """rootに近い順にedgeを回すIterator""" N, ts, ch = self.N, self.ts_order, self.children if self._has_weight: wei, en = self.weight, self.encode for v in ts: for c in ch[v]: yield (v,c,wei[en(v,c)]) else: for v in ts: for c in ch[v]: yield (v,c) """ weight """ #edge->weightにO(1)でアクセスできるようにdictで持つ def set_weight(self, edge): assert self._has_weight == False d = {} for u,v,c in edge: d[self.encode(u,v)] = d[self.encode(v,u)] = c self.weight = d self._has_weight = True def get_weight(self, u, v) -> int: return self.weight[self.encode(u, v)] """depth : rootからの深さ""" def get_depth(self, v) -> int: # obj.depth[v] と同じ. if not hasattr(self, "depth"): self.build_depth() return self.depth[v] def build_depth(self): assert self._rooted N, ch, ts = self.N, self.children, self.ts_order depth = [0]*N for v in ts: for c in ch[v]: depth[c] = depth[v] + 1 self.depth = depth """subtree_size : 部分木""" def build_des_size(self): assert self._rooted if hasattr(self, "des_size"): return N, ts, par = self.N, self.ts_order, self.parent des = [1]*N for i in range(N-1,0,-1): v = ts[i] p = par[v] des[p] += des[v] self.des_size = des """centroid : 重心分解""" def centroid_decomposition(self, build_dist=True): """ centroid_id[i] : DFS的に重心分解をしたとき, 頂点iを重心とする重心木が何番目に登場するか. 頂点cenを重心とする重心木の頂点を探索する際は,頂点cenから, T.is_id_larger(v, cen)==True な頂点vのみを使って到達可能な頂点vを探索すればいい. centroid_dfs_order : centroid_id の逆順列. reveresed(centroid_dfs_order)順に重心木を探索することで より小さい重心木についての結果を用いたDPが可能. """ if hasattr(self, "centroid_id"): return # 根に依存しないアルゴリズムなので根0にしていい. if not self._rooted: self.set_root(0) if not hasattr(self, "des_size"): self.build_des_size() # sizeは書き換えるのでコピーを使用. N, G, size = self.N, self.G, self.des_size[:] c_id, c_depth, c_par, c_dfs_order = [-1]*N, [-1]*N, [-1]*N, [] stack = [(self.root, -1, 0)] # 重心を見つけたら,「重心分解後のその頂点が重心となる部分木」の # DFS順の順番, 深さ, 重心木における親にあたる部分木の重心を記録 for order in range(N): v, prev, d = stack.pop() while True: for adj in G[v]: if c_id[adj] == -1 and size[adj]*2 > size[v]: # adjを今見ている部分木の根にし,sizeを書き換える. size[v], size[adj], v = size[v]-size[adj], size[v], adj break else: break c_id[v], c_depth[v], c_par[v] = order, d, prev c_dfs_order.append(v) if size[v] > 1: for adj in G[v]: if c_id[adj] == -1: stack.append((adj, v, d+1)) self.centroid_id, self.centroid_depth, self.centroid_parent, self.centroid_dfs_order = c_id, c_depth, c_par, c_dfs_order if build_dist == True: self.build_centroid_dist() def build_centroid_dist(self): """ 重心同士を結んだ木を重心分解木と呼ぶことにする. 重心分解木のみを考えて解けるなら楽だが、 「各重心木における重心(根)との距離」 を求めるには元の辺の情報が必要.一方それさえ求めれば、 重心分解木に対する考察だけで足りる問題が多い. """ if hasattr(self, "centroid_dist"): return False if not hasattr(self, "centroid_id"): self.centroid_decomposition() N, G, c_depth = self.N, self.G ,self.centroid_depth is_id_larger = self.is_id_larger log = max(c_depth) + 1 # dist[d][v] : vが深さdの重心木に属しているならその重心からの距離. dist = [[-1]*N for _ in range(log)] for cen in range(N): d = c_depth[cen] stack = [cen] dist[d][cen] = 0 while stack: v = stack.pop() for adj in G[v]: if dist[d][adj] == -1 and is_id_larger(adj, cen): if self._has_weight: dist[d][adj] = dist[d][v] + self.weight[self.encode(v, adj)] else: dist[d][adj] = dist[d][v] + 1 stack.append(adj) self.centroid_log, self.centroid_dist = log, dist def is_member_of_centroid_tree(self, v, c): # 頂点vが重心cの重心木に属するかを判定 O(logN) vs = self.get_higher_centroids_with_self(v) return c in vs def is_id_larger(self, u, v): # 重心cからBFSする時に、is_id_larger(adj, c)とすれば重心木内部を探索できる. return self.centroid_id[u] > self.centroid_id[v] def get_higher_centroids_with_self(self, c): # 頂点cが属する重心木の重心をサイズの昇順に列挙. O(logN) vs = [] for d in range(self.centroid_depth[c], -1, -1): vs.append(c) c = self.centroid_parent[c] return vs def yield_centroid_children(self, v): # 頂点vを重心とする重心木における, # 「『vの子供を根とした部分木』と構成が同じ重心木の重心」を列挙する. # 「『重心木』の木」における「『vを重心とする重心木』の子の重心木」の重心 ともいえる. G, is_id_larger, c_par = self.G, self.is_id_larger, self.centroid_parent for ch in G[v]: if is_id_larger(ch, v): ch_cen = ch while c_par[ch_cen] != v: ch_cen = c_par[ch_cen] yield (ch, ch_cen) def find_lowest_common_centroid(self, u, v): # 頂点u,vをどちらも含む最小の重心木を返す. O(logN) c_depth, c_par = self.centroid_depth, self.centroid_parent du, dv = c_depth[u], c_depth[v] if du > dv: u,v = v,u du,dv = dv,du for _ in range(dv - du): v = c_par[v] while u != v: u,v = c_par[u],c_par[v] return u def build_the_centroid(self): """ 全体の重心だけで十分な時用 O(N) """ if not self._rooted: self.set_root(0) if hasattr(self, "the_centroid"): return False if hasattr(self, "centroid_id"): self.the_centroid = self.centroid_id[0] return True if not hasattr(self, "des_size"): self.build_des_size() N, ch, size = self.N, self.children, self.des_size v = self.root while True: for c in ch[v]: if size[c] > N // 2: v = c break else: self.the_centroid = v return True def get_the_centroid(self): if hasattr(self, "centroid_id"): return self.centroid_id[0] if not hasattr(self, "the_centroid"): self.build_the_centroid() return self.the_centroid """ tree dp """ def dp_from_leaf(self, merge, e, add_root, push=lambda obj,data,dst,src:data): """ チートシート 部分木の大きさ : dp_from_leaf(lambda x,y:x+y, 0, lambda x,y,z:y+1) """ assert self._rooted # pushで形整えたデータを親の単位元で初期化されたノードにmerge. # 子が全部mergeされたらadd_rootで自身の頂点の情報を追加. N, ts, par = self.N, self.ts_order, self.parent sub = [e] * N for i in range(N-1,-1,-1): v = ts[i] sub[v] = add_root(self, sub[v], v) p = par[v] if p != -1: sub[p] = merge(sub[p], push(self, sub[v], p, v)) return sub def rerooting_dp(self, merge, e, add_root, push=lambda obj,data,dst,src:data): """全方位木DP 途中で頂点を変更する""" if self._rooted == False: self.set_root(0) sub = self.dp_from_leaf(merge, e, add_root, push) N = self.N ts, par, ch = self.ts_order, self.parent, self.children compl, dp = [e]*N, [e]*N for i in range(N): v = ts[i] p, size = par[v], len(ch[v]) left, right = [e]*size, [e]*size for j in range(size): c = ch[v][j] left[j] = merge(left[j-1] if j>0 else e, push(self, sub[c], v, c)) for j in range(size-1,-1,-1): c = ch[v][j] right[j] = merge(right[j+1] if j0 else e) compl[c] = merge(compl[c], right[j+1] if j children[v] のdist """ N, G = self.N, self.G dist, que = [None]*N, [v] dist[v] = 0 if self._has_weight: wei, en = self.weight, self.encode else: wei, en = [1], lambda a,b:0 while que: v = que.pop() for adj in G[v]: if dist[adj] is None: dist[adj] = op(dist[v], wei[en(v, adj)]) que.append(adj) return dist def build_diameter(self): """直径を求める""" self.build_dist_from_root() if hasattr(self, "diameter"): return dist_r = self.dist_from_root v = dist_r.index(max(dist_r)) dist_v = self.calc_dist_from_a_node(v) dia = max(dist_v) u = dist_v.index(dia) self.diameter, self.end_points_of_diameter = dia, [v, u] def get_diameter(self): """直径の取得""" if hasattr(self, "diameter"): return self.diameter self.build_diameter() return self.diameter main() """==================fold line 1800=================="""