Harryxun/stf_run huggingface dataset:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M = map(int,input().split())
uf = UnionFind(N)
for i in range(M):
         a,b = map(int,input().split())
         uf.union(a,b)
         

print(uf.group_count() - 1)


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M = map(int,input().split())
uf = UnionFind(N)

for i in range(M):
         a,b = map(int,input().split())
         uf.union(a-1,b-1)
         

print(uf.group_count() - 1)
#!/usr/bin/env python3
# coding=utf-8

import sys

import numpy as np

n, k = map(int, sys.stdin.readline().strip().split(" "))
xyc = [l.strip().split(" ") for l in sys.stdin.readlines()]
xy = [tuple((int(_x), int(_y) if _c == "W" else int(_y) + k)) for (_x, _y, _c) in xyc]
xy = [tuple((_x % (2 * k), _y % (2 * k))) for (_x, _y) in xy]

check = np.zeros((n, 2 * k, 2 * k))
for _i, (_x, _y) in enumerate(xy):
    check[_i, _x:_x + k, :] = 1
    if _x > k:
        check[_i, :_x - k, :] = 1
    check[_i, :, _y:_y + k] = 1 - check[_i, :, _y:_y + k]
    if _y > k:
        check[_i, :, :_y - k] = 1 - check[_i, :, :_y - k]
    check[_i] = 1 - check[_i]
print(int(np.max(np.sum(check, axis=0))))

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
ub = K * 2
b = [[0 for j in range(ub + 1)] for i in range(ub + 1)]
ADD = {"B": 0, "W": K}


def create_bound(p, K, ub):
    if p - K + 1 >= 0:
        return [(p - K + 1, p + 1)]
    else:
        return [(0, p + 1), ((p - K + 1) % ub, ub)]


for i in range(N):
    x, y, c = input().split()
    nx = int(x) % ub
    ny = (int(y) + ADD[c]) % ub
    for add in [0, K]:
        for xlb, xub in create_bound((nx + add) % ub, K, ub):
            for ylb, yub in create_bound((ny + add) % ub, K, ub):
                b[xlb][ylb] += 1
                b[xlb][yub] -= 1
                b[xub][ylb] -= 1
                b[xub][yub] += 1

b_arr = np.array(b)
for i in range(ub):
    b_arr[i + 1, :] += b_arr[i, :]
for j in range(ub):
    b_arr[:, j + 1] += b_arr[:, j]
print(b_arr.max())
a,b,c=map(int,input().split())
L[a,b,c]
L.sort()
print(L[2]*10+L[1]+L[0])


### FIXED CODE ###

a,b,c=map(int,input().split())
L=[a,b,c]
L.sort()
print(L[2]*10+L[1]+L[0])
from collections import deque
N,u,v = map(int,input().split())
E = [[] for _ in range(N + 1)]
for i in range(N-1):
    a,b = map(int,input().split())
    E[a].append(b)
    E[b].append(a)
print(E)
def bfs(start,N,AB):
    d = [-1]*(N+1)
    d[start] = 0
    q = [start]
    while q:
        print(d,q)
        v = q.pop()
        cnt = d[v]+1
        for i in E[v]:
            if(d[i] == -1):
                q.append(i)
                d[i] = cnt
    return d
taka = bfs(u,N,AB)#takahashi
aoki = bfs(v,N,AB)
print(taka,aoki)
fin = -1
for i in range(N+1):
    if(taka[i] < aoki[i]):
        fin = max(fin,aoki[i])
        ans = fin - (aoki[i]-taka[i]+1)//2
print(ans)

### FIXED CODE ###

N,u,v = map(int,input().split())
E = [[] for _ in range(N + 1)]
for i in range(N-1):
    a,b = map(int,input().split())
    E[a].append(b)
    E[b].append(a)
#print(E)
def bfs(start,N):
    d = [-1]*(N+1)
    d[start] = 0
    q = [start]
    while q:
        #print(d,q)
        v = q.pop()
        cnt = d[v]+1
        for i in E[v]:
            if(d[i] == -1):
                q.append(i)
                d[i] = cnt
    return d
taka = bfs(u,N)
aoki = bfs(v,N)
#print(taka,aoki)
fin = 0
for i in range(N+1):
    if(taka[i] < aoki[i]):
        fin = max(fin,aoki[i])
print(fin - 1)
def main():
    n = int(input())
    a = [int(input()) for _ in [0]*n]
    m = max(a)
    xor = 0
    for i in a:
        xor ^= i
    i = 1
    cnt = 0
    while True:
        if xor >= i:
            i *= 2
            cnt += 1
        else:
            break
    ans = 0
    for i in range(cnt-1, -1, -1):
        j = (xor & 2**i) // (2**i)
        if j == 1:
            for k in a:
                if k % (2**i) == 0:
                    xor ^= k
                    xor ^= k-1
                    ans += 1
                    a.remove(k)
                    break
            else:
                print(-1/0)
                return 0
    print(ans)


main()

### FIXED CODE ###

def main():
    n = int(input())
    a = [int(input()) for _ in [0]*n]
    xor = 0
    for i in a:
        xor ^= i
    i = 1
    cnt = 0
    while True:
        if xor >= i:
            i *= 2
            cnt += 1
        else:
            break
    ans = 0
    for i in range(cnt-1, -1, -1):
        j = (xor & 2**i) // (2**i)
        if j == 1:
            for k in a:
                if (k & 2**i) // (2**i) == 1 and k % (2**i) == 0:
                    xor ^= k
                    xor ^= k-1
                    ans += 1
                    a.remove(k)
                    break
            else:
                print(-1)
                return 0
    print(ans)


main()
s = list(map(int,input().split()))
t = s.pop(0)
s.sort()
c = 1
d = 0
for i in range(t):
  for k in range(0,i):
    if s[i]%s[k]==0:
      c = 0
      break
  if c == 1:
    d = d+1
print(d)
  
    

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
M = 10**6 + 1
cnt = [0] * M
for a in A:
    if cnt[a] != 0:
        cnt[a] += 1
        continue
    for b in range(a, M, a):
        cnt[b] += 1
ans = 0
for a in A:
    if cnt[a] == 1:ans += 1
print(ans)
import sympy
N = int(input())
count = 0
for i in range(N+1):
    count += (i * len(sympy.divisors(i)))

print(count)

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1,N+1):
    ans += (N//i)*(i+(i*(N//i)))//2
print(ans)
from collections import Counter
n = int(input())
V = list(map(int,input().split()))
A = Counter(V[0::2]).most_common(2)
A = Counter(V[1::2]).most_common(2)
A.append((0,0))
A.append((0,0))
if A[0][0]!=B[0][0]:
    print(n-(A[0][1]+B[0][1]))
else:
    print(min(n-(A[1][1]+B[0][1]),n-(A[0][1]+B[1][1])))


### FIXED CODE ###

from collections import Counter
n = int(input())
V = list(map(int,input().split()))
A = Counter(V[0::2]).most_common(2)
B = Counter(V[1::2]).most_common(2)
A.append((0,0))
B.append((0,0))
if A[0][0]!=B[0][0]:
    print(n-(A[0][1]+B[0][1]))
else:
    print(min(n-(A[1][1]+B[0][1]),n-(A[0][1]+B[1][1])))
N,M=map(int,input().split())
lines=[]
lines_s=[]
ans=0
for line in range(M):
	s,c=map(int,input().split())
	if N>=s and s not in lines_s:
		ans+=c*(10**(N-s))
		lines.append([s,c])
		lines_s.append(s)
	elif [s,c] in lines:
		continue

	else:
		break

if len(ans)==N:
	print(ans)
else:
	print(-1)



### FIXED CODE ###

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))





n,m=input2()
sc_list=[]
for _ in range(m):
	sc_list.append(input_array())

result=0
flag=True
result_dict={}
for sc in sc_list:
	sc0=sc[0]
	sc1=sc[1]
	if n!=1 and sc0==1 and sc1==0:
		#2桁以上かつ先頭が0である
		flag=False
		break
	elif sc0 in result_dict:
		if result_dict[sc0]==sc1:
			#既に入力済である場合
			continue
		else:
			#数字の衝突
			flag=False
			break
	else:
		result+=10**(n-sc0)*sc1
		result_dict[sc0]=sc1

if len(str(result))<n:
	result+=10**(n-1)

if flag:
	print(result)
else:
	print(-1)
o = list(input())
e = list(input())
if len(o) > len(e):
  e.add("")
for i in range(o):
  print(o[i] + e[i], end='')

### FIXED CODE ###

o, e = [input().rstrip() for i in range(2)]
lst = []
for i in range(len(o)):
    print(o[i], end='')

    if i + 1 > len(e):
        print()
        break
    else:
        print(e[i], end='')
n,h =map(int,input().split())
a,b = [0]*n,[0]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())
c = h//max(a) + [1,0][h%max(a)==0]
if sum(b) >= h:
    c0 = 1
    d = 0
    e = list(reversed(sorted(b)))
    while d < h:
        d += e[i] 
        c0 += 1
        i += 1
    c = min(c,c0)
print(c)

### FIXED CODE ###

n,h =map(int,input().split())
a,b = [0]*n,[0]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())
A = max(a)
s = list()
for i in range(n):
    if b[i] > A:
        s.append(b[i])
s.sort()
s.reverse()
c = sum(s)
if c < h:
    print(len(s) + (h-c)//A + [1,0][(h-c)%A==0])
else:
    S = 0
    for i in range(len(s)):
        S += s[i]
        if S >= h:
            print(i+1)
            break
n=input().split()
m=int(n[0])
c=int(n[1])
d=int(n[2])
sorted(m,c,d)
print(m[0],c[1],d[2])


### FIXED CODE ###

n=list(map(int, input().split()))
n.sort()
print(n[0],n[1],n[2])
while True:
    n, m = map(int, input().split())
    dpList = []
    if n + m < 1:
        break
    for i in range(n):
        row = list(map(int,input().split()))
        dpList.append(row)
        dpList = sorted(dpList, key = lambda x:x[1], reverse = True)
    for i in range(n):
        if m - dpList[i][0] <= 0:
            num = (dpList[i][0] - m) * dpList[i][1]
            for j in range(i + 1, n):
                num += dpList[j][0] * dpList[j][1] 
            print(num)
            break
        else:
            m -= dpList[i][0]

### FIXED CODE ###

while True:
    n, m = map(int, input().split())
    dpList = []
    if (n,m) == (0,0):
        break
    for i in range(n):
        row = list(map(int,input().split()))
        dpList.append(row)
    dpList = sorted(dpList, key = lambda x:x[1], reverse = True)
    num = 0
    for i in range(n):
        if m >= dpList[i][0]:
            m -= dpList[i][0]
        else:
            num += (dpList[i][0] - m) * dpList[i][1]
            m = 0
    print(num)
N,M = map(int, input().split())
K = list(map(int, input().split()))
del K[0]
for i in range(N):
    k = list(map(int, input().split()))
    del k[0]
    K = list(set(k) & set(K))
print(len(K))


### FIXED CODE ###

N,M = map(int, input().split())
K = list(map(int, input().split()))
del K[0]
for i in range(N - 1):
    k = list(map(int, input().split()))
    del k[0]
    K = list(set(k) & set(K))
print(len(K))
# coding:utf-8
# Doubly Linked List

class DLL:

    def __init__(self):
        self.array = []

    def insert(self, x):
        self.array = [x] + self.array
    
    def delete(self, x):
        del self.array[self.array.index(x)]

    def deleteFirst(self):
        del self.array[0]

    def deleteLast(self):
        del self.array[len(self.array)-1]


def main():

    dll = DLL()
    n = int(input())

    for _ in range(n):
        key = ''
        try:
            command, key = map(str, input().split())

        except ValueError:
            command = input()

        print(command, key)
        eval("dll." + command + '(' + key + ')')

    print(dll.array)

if __name__ == "__main__":
    main()

### FIXED CODE ###

# coding:utf-8
# Doubly Linked List

from collections import deque

def main():

    n = int(input())
    dll = deque()

    for _ in range(n):
        operation = input().split(' ')
        if operation[0] in ["insert", "delete"]:
            key = operation[1]
            if operation[0] == "insert":
                dll.appendleft(key)
            else:
                try:
                    dll.remove(key)
                except:
                    pass

        else:
            if operation[0][6] == 'F':
                dll.popleft()

            else:
                dll.pop()

    print(' '.join(dll))

if __name__ == "__main__":
    main()
N = input()
N = int(N)

a_sub = input().split(" ")
a = [int(n0) for n0 in a_sub]
# print(a)

b_sub = input().split(" ")
b = [int(n0) for n0 in b_sub]
# print(b)

c_sub = input().split(" ")
c = [int(n0) for n0 in c_sub]
# print(c)

score = 0
for xi in range(N-1):
    score = score + b[xi]
    if a[xi+1]==a[xi]+1:
        score = score + c[a[xi]-1]
        # print(xi, c[xi])
score = score + b[N-1]
print(score)


### FIXED CODE ###

N = input()
N = int(N)
print(N**3)
a,b = [int(i) for i in input().split()]
A = max(a,b)
B = max(a,b)
a_list=[]
for k in range(b):
	a_list.append(a)
print(''.join(map(str,a_list))

### FIXED CODE ###

a,b = [int(i) for i in input().split()]
A = max(a,b)
B = min(a,b)
a_list=[]
for _ in range(A):
	a_list.append(B)
print(''.join(map(str,a_list)))
import bisect
a=[]
def f(a,bin,n):
    if bin>n:return
    if bin:a+=[bin]
    f(a,bin*10+2,n)
    f(a,bin*10+8,n)

def g(n,p):
    m=-1<<20
    x=bisect.bisect_left(a,n)
    if x!=len(a) and a[x]==n:m=1
    if a[p]**2>n:return m
    if n%a[p]==0:m=g(n//a[p],p)+1
    return max(m,g(n,p+1))

n=int(input())
if n&1:print(-1);exit()
f(a,0,n)
a=sorted(a)+[10**20]
b=g(n,0)
if b<0:b=-1
print(b)

### FIXED CODE ###

import bisect
import sys
sys.setrecursionlimit(10000)
a=[]
def f(a,bin,n):
    if bin>n:return
    if bin:a+=[bin]
    f(a,bin*10+2,n)
    f(a,bin*10+8,n)

def g(n,p):
    m=-1<<20
    x=bisect.bisect_left(a,n)
    if x!=len(a) and a[x]==n:m=1
    if a[p]**2>n:return m
    if n%a[p]==0:m=g(n//a[p],p)+1
    return max(m,g(n,p+1))

n=int(input())
if n&1:print(-1);exit()
f(a,0,n)
a=sorted(a)
b=g(n,0)
if b<0:b=-1
print(b)
from functools import lru_cache

@lru_cache(maxsize=1000)
def judge(x,L):
    for l in L:
        if x[1]>l[0] and x[0] <l[1]:
            return False
    else:
        return True

n=int(input())
X=[]
L=[]
A=[]
B=[]
for _ in range(n):
    x,l=map(int,input().split())
    X.append(x)
    L.append(l)
    A.append(x-l)
    B.append(x+l)
k = zip(L,X,A,B)
k = sorted(k, key=lambda x:(x[1], x[2]))
c=1
ans=[]
ans.append((k[0][2],k[0][3]))

for i in range(1,n):
    x=(k[i][2],k[i][3])
    if judge(x,ans):
        ans.append(x)
        c+=1
print(c)

### FIXED CODE ###

n=int(input())
itv=[]
for _ in range(n):
    x,l=map(int,input().split())
    itv.append((x+l,x-l))
itv.sort()
ass = 0
tt = -float("inf")
for i in range(n):
    if tt <= itv[i][1]:
        ass += 1
        tt = itv[i][0]
print(ass)
N, K = map(int, input().split())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    

dots = XY[:]

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(x, y) for x, y in dots]
y_dots = sorted(y_dots, key=lambda x: x[1])

ans = INT_MAX
for l in range(N):
    for r in range(l+1, N+1):
        for u in range(N):
            for t in range(u+1, N+1):
                xy_dots =  set(x_dots[l:r]) & set(y_dots[u:t])
                if len(xy_dots) >= K:
                    #print("---")
                    #print(l, r, x_dots[l:r])
                    #print(u, t, y_dots[u:t])
                    l = x_dots[l:r][0][0]
                    r = x_dots[l:r][-1][0]
                    u = y_dots[u:t][0][1]
                    t = y_dots[u:t][-1][1]
                    #print((r-l)*(t-u))
                    ans = min(ans, (r-l)*(t-u))
print(ans)


#y_dots = sorted(y_dots, key=lambda x: x[1])
#ans = INT_MAX


### FIXED CODE ###

N, K = map(int, input().split())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)
import sys
import bisect
input = sys.stdin.readline

a,b,q = map(int, input().split())
s = [-1 for i in range(a)]
t = [-1 for i in range(b)]

for i in range(a):
	S = int(input())
    s[i] = S
    
for i in range(b):
	T = int(input())
    t[i] = T
    
s.sort()
t.sort()

for i in range(q):
	x = int(input())
    slidx = bisect.bisect_left(s, x)
    tlidx = bisect.bisect_left(t, x) 
	sl = x - s[slidx]
	tl = x - t[tlidx]
    tr = 90000000000 - x
    sr = 90000000000 - x
    if slidx < a-1:
      sr = s[slidx+1] - x
    if slidx < b-1:
      tr = t[tlidx+1] - x
    dist = min( max(sl,tl), max(sr,tr), min(sr, sl)*2 + min(tr,tl), min(tr,tl)*2 + min(sr,sl))
    print(dist)

### FIXED CODE ###

import sys
import bisect
input = sys.stdin.readline

a,b,q = map(int,input().split())

s = [-1 for i in range(a)]
t = [-1 for i in range(b)]

for i in range(a):
	S = int(input())
	s[i] = S
    
for i in range(b):
	T = int(input())
	t[i] = T
    
s.sort()
t.sort()
for i in range(q):
	x = int(input())

	slidx = bisect.bisect_left(s, x) -1
	tlidx = bisect.bisect_left(t, x) -1
	sl = -20000000000
	tl = -20000000000
	sr = 20000000000
	tr = 20000000000
	if slidx >= 0:
		sl = s[slidx]
	if tlidx >= 0:
		tl = t[tlidx]

	if slidx < a-1:
		sr = s[slidx+1]
	if tlidx < b-1:
		tr = t[tlidx+1]
	sl = x - sl
	tl = x - tl
	sr = sr - x
	tr = tr - x
	#print([sl,tl,sr,tr])
	dist = min( [max(sl,tl), max(sr,tr), min(sr, sl)*2 + min(tr,tl), min(tr,tl)*2 + min(sr,sl)])
	print(dist)
n, a, b = map(int,input().split())
if n＊a < b:
  print(int(n＊a))
elif n＊a >= b:
  print(int(b))


### FIXED CODE ###

n, a, b = map(int,input().split())
if n*a > b:
  print(b)
else:
  print(n*a)
import sys

N = int(input())
ABList = []
for i in range(N):
    ABList.append(sys.stdin.readline().split())
sABList = sorted(ABList, key=[1])
temp = 0
isYes = True
for i in reversed(range(0, len(sABList))):
    temp += int(sABList[i][0])
    if temp > int(sABList[i][1]):
        isYes = False
print(sABList)
print(["No", "Yes"][isYes])


### FIXED CODE ###

N = int(input())
works = []
for i in range(N):
    works.append(list(map(int, input().split())))
works = sorted(works, key=lambda x: (x[1], x[0]))
time = 0
isFail = False
for i in range(N):
    time += works[i][0]
    if time > works[i][1]:
        isFail = True
        break
print("YNeos"[isFail::2])
A = int(input())
B = list(map(int, input().split()))  

dai=[0, 0, 0, 0, 0]
for i, l in enumerate(B):
  if i==0:
    continue
  if B[i-1]-B[i]>0:
    dai[i]=B[i-1]-B[i]
    #B[i]+=B[i-1]-B[i]
    
print(sum(dai))

### FIXED CODE ###

A = int(input())
B = list(map(int, input().split()))  

dai=[0 for _ in range(A)]

for i, l in enumerate(B):
  if i==0:
    continue
  if B[i-1]-B[i]>0:
    dai[i]=B[i-1]-B[i]
    B[i]+=B[i-1]-B[i]

print(sum(dai))
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
c.sort()
ans = 0
for i in range(n):
    x = bisect.bisect_left(a, b[i])
    y = bisect.bisect_right(c, b[i])
    ans += x * (n - y)
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
c.sort()
ans = 0
for i in range(n):
    x = bisect.bisect_left(a, b[i])
    y = bisect.bisect_right(c, b[i])
    ans += x * (n - y)
print(ans)
S = input()
print(S.count('+')-S.count'-')


### FIXED CODE ###

S = input()
print(S.count('+')-S.count('-'))
H,A =map(int,input())
print((H//A)+1)


### FIXED CODE ###

H,A =map(int,input().split())
print(H//A+(1 if not H%A==0 else 0))
n = int(input())
A = [int(i) for i in input().split()]
A.insert(0, 0)
dp = list([0] * 2 for i in range(n+1))
dp[0][0] = 0
dp[0][1] = -1000000000000
for i in range(1, n) :
    dp[i][0] = max(dp[i-1][0] + A[i], dp[i-1][1] - A[i])
    dp[i][1] = max(dp[i-1][0] - A[i], dp[i-1][1] + A[i])
ans = max(dp[n-1][0] + A[n], dp[n-1][1] - A[n])    

print(ans)


### FIXED CODE ###

A, B, T = map(int, input().split())
Ans  = T // A * B
print(Ans)
x = input()

if x >= 30:
  print("yes")
else:
  print("no")

### FIXED CODE ###

x = input()

if int(x) >= 30:
  print("Yes")
else:
  print("No")
from math import *
a,b=map(int,input().split())
s=input()
t=input()
ans=a*b//gcd(a,b)
if a%b==0:
    if not all(s[i]==t[1+i*a//b] for i in range(b)):ans=-1
if b%a==0:
    if not all(t[i]==s[1+i*b//a] for i in range(a)):ans=-1
if s[0]!=t[0]:
    ans=-1
print(ans)

### FIXED CODE ###

from math import *
a,b=map(int,input().split())
s=input()
t=input()
g=gcd(a,b)
for i in range(g):
    if s[a//g*i]!=t[b//g*i]:
        print(-1)
        exit()
print(a*b//g)
n = int(input())
a = []
for i in range(n):
    a.append(input())

for i in range(n):
    a.append(a[i])


x = 0

for i in range(n):
    for j in range(n):
        for k in range(j+1):
            if a[i+j][k]==a[i+k][j]:
                continue
            else:
                break
        else:
            continue
        break
    else:
        x += 1

print(n*x)

 

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))

s = []
p = 0

for i in range(n):
    p+=a[i]
    s.append(p)
s.append(0)

x = 0
import collections
s = collections.Counter(s)

y,z = zip(*s.most_common())

for i in range(len(z)):
    x += (z[i]*(z[i]-1))//2
print(x)