Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
from collections import deque

readline = sys.stdin.buffer.readline

def main():
    n = int(readline().rstrip())
    p = list(map(int, readline().split()))
    diag = [-1, 1, n, -n]
    V = (n + 2)**2
    st = [1] * V
    gr = [0] * V
    ans = 0
    for i in range(n):
        for j in range(n):
            gr[i*n + j + n + 1] = min(min(i, j), n-1-max(i, j))
    for v in p:
        v += n
        ans += gr[v]
        st[v] = 0
        c = min([gr[v+dv] + st[v+dv] for dv in diag])
        if c < gr[v]:
            gr[v] = c
        q = deque()
        q.append(v)
        while q:
            v = q.popleft()
            for dv in diag:
                nv = v + dv
                if gr[nv] > gr[v] + st[v]:
                    gr[nv] = gr[v] + st[v]
                    if st[v] > 0:
                        q.append(nv)
                    else:
                        q.appendleft(nv)
    print(ans)
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque

readline = sys.stdin.readline
ni = lambda: int(readline().rstrip())
nl = lambda: list(map(int, readline().split()))

def solve():
    n = ni()
    p = nl()
    diag = [-1, 1, n, -n]
    st = [1]*(n+2)**2
    gr = [0]*(n+2)**2
    ans = 0
    for i in range(n):
        for j in range(n):
            gr[i*n + j + n + 1] = min(min(i, j), n-1-max(i, j))
    for v in p:
        v += n
        ans += gr[v]
        st[v] = 0
        c = gr[v]
        for dv in diag:
            nv = v + dv
            c = min(c, gr[nv] + st[nv])
        gr[v]= c
        q = deque()
        q.append(v)
        while q:
            v = q.popleft()
            for dv in diag:
                nv = v + dv
                if gr[nv] > gr[v] + st[v]:
                    gr[nv] = gr[v] + st[v]
                    if st[v]:
                        q.append(nv)
                    else:
                        q.appendleft(nv)
    print(ans)
    return

if __name__ == '__main__':
    solve()
### BUGGY CODE ###

import itertools

s = input()
t = input()
obj = {}

loop_num = 0
temp_num = -1

for i in range(len(s)):
    char = s[i]
    if not (char in obj):
        obj[char] = [i]
    else:
        obj[char].append(i)

for i in range(len(t)):
    char = t[i]
    if not (char in obj):
        loop_num = -1
        break
    else:
        next_num = next(itertools.filterfalse(lambda x: x <= temp_num, obj[char]), None)
        if next_num == None:
            loop_num += 1
            temp_num = obj[char][0]
        else:
            temp_num = next_num

if(loop_num == -1):
    print(-1)
else:
    print(loop_num * len(s) + temp_num + 1)

### FIXED CODE ###

from bisect import bisect_right

s = input()
t = input()
obj = {}

loop_num = 0
temp_num = -1

for i in range(len(s)):
    char = s[i]
    if not (char in obj):
        obj[char] = [i]
    else:
        obj[char].append(i)

for i in range(len(t)):
    char = t[i]
    if not (char in obj):
        loop_num = -1
        break
    else:
        next_index = bisect_right(obj[char], temp_num)
        if next_index == len(obj[char]):
            loop_num += 1
            temp_num = obj[char][0]
        else:
            temp_num = obj[char][next_index]

if(loop_num == -1):
    print(-1)
else:
    print(loop_num * len(s) + temp_num + 1)
### BUGGY CODE ###



def read_input():
    n = int(input())
    alist = list(map(int, input().split()))

    return n, alist


def possibility_check(n, alist):
    occurs = {}
    for a in alist:
        if a in occurs.keys():
            occurs[a] += 1
        else:
            occurs[a] = 1

    if n % 2:
        if occurs[0] == 1:
            for i in range(2, n, 2):
                if occurs[i] != 2:
                    return False
            return True
        else:
            return False
    else:
        for i in range(1, n, 2):
            if occurs[i] != 2:
                return False
        return True

def submit():
    n, alist = read_input()

    if possibility_check(n, alist):
        # ans = (2 ** (n // 2)) % (10**9 + 7)
        ans = 1
        for i in range(n // 2):
            ans *= 2
            if ans > 10**9 + 7:
                ans %= (10**9 + 7)
        print(ans)
    else:
        print(0)


if __name__ == '__main__':
    submit()


### FIXED CODE ###



def read_input():
    n = int(input())
    alist = list(map(int, input().split()))

    return n, alist


def possibility_check(n, alist):
    alist.sort()

    if n % 2:
        even = [x for x in range(2, n) if x % 2 == 0]
        comp = [0] + even + even
        comp.sort()

    else:
        odd = [x for x in range(1, n) if x % 2 == 1]
        comp = odd + odd
        comp.sort()

    if alist == comp:
        return True
    else:
        return False


def submit():
    n, alist = read_input()

    if possibility_check(n, alist):
        # ans = (2 ** (n // 2)) % (10**9 + 7)
        ans = 1
        for i in range(n // 2):
            ans *= 2
            if ans > 10**9 + 7:
                ans %= (10**9 + 7)
        print(ans)
    else:
        print(0)


if __name__ == '__main__':
    submit()
### BUGGY CODE ###

import copy
import bisect
def f(x):
    return int(x) - 1

N = int(input())
A = map(f, input().split())
C = [0]*N
for a in A:
    C[a] += 1
sorted_C = sorted(C)

def h(L, i):
    """
    sorted_C[N - i : N]の最小の所に、sorted_C[ : N - i]を順番に積み上げるイメージ
    """
    if i == 1:
        return N
    
    for j in range(N - i - 1, - 1, - 1):
        if L[j] == 0:
            return L[N - i]
        
        L[N - i] += L[j]
        a = bisect.bisect_right(L[N - i + 1 : ], L[N - i])
        L[N - i:] = L[N - i + 1: N - i + 1 + a] + [L[N - i]] + L[N - i + 1 + a :]
        # L[i -1]が大きくなったからソートし直す
        # これはL[0 : i - 2]はソート済みだからbisectでL[0 : i - 2]にL[i - 1]が入るいちを見つければ良い。下の解答参照
    return L[N - i]
        
for i in range(N):
    L = copy.copy(sorted_C)
    print(h(L, i + 1))

### FIXED CODE ###

N = int(input())
A = map(int, input().split())
C = [0]*N
for a in A:
    C[a - 1] += 1
D = [0]*(N + 1)
for c in C:
    D[c] += 1

Dk_accum = [0]*(N + 1)
for i in range(1, N + 1):
    Dk_accum[i] = Dk_accum[i - 1] + i*D[i]
    
D_sum = sum(D)
D_accum = [0]*(N + 2)
D_accum[0] = D_sum
for i in range(1, N + 1):
    D_accum[i] = D_accum[i - 1] - D[i - 1]
    
F = [0]*(N + 1)
for i in range(1, N + 1):
    F[i] = (Dk_accum[i]//i + D_accum[i + 1])

i = N
for K in range(1, N + 1):
    while i > 0 and K > F[i]:
        i -= 1
    print(i)
### BUGGY CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string,scipy
import sys
sys.setrecursionlimit(10**7)

def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    N,K = LI()
    P = LI()
    # Pk_max_idx = numpy.argmax(numpy.convolve(P,numpy.ones(K)/K,mode="valid"))
    # Pk_max_idx = (numpy.max(numpy.convolve(P,numpy.ones(K)/K,mode="valid"))+1)*(K/2)
    # print((sum(P[Pk_max_idx:Pk_max_idx+K])+K)/2)
    print((numpy.max(scipy.convolve(P,numpy.ones(K,dtype='float'), mode='valid')/scipy.convolve(numpy.ones(len(P)),numpy.ones(K),mode='valid'))+1)*(K/2))
    # print((numpy.max(numpy.convolve(P,numpy.ones(K)/K,mode="valid"))+1)*(K/2))
main()



### FIXED CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string,scipy
import sys
sys.setrecursionlimit(10**7)

def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    N,K = LI()
    P = LI()
    Pe = [(v+1)/2 for v in P]
    P_ms = numpy.cumsum(Pe)
    if K==N:print("{:.12f}".format(sum(Pe)));exit(0)
    ans = 0
    for i in range(K,N):
        ans = max(ans,P_ms[i]-P_ms[i-K])
    print("{:.12f}".format(ans))
main()
### BUGGY CODE ###

from scipy.misc import comb
N = int(input())
A = list(map(int,input().split()))
A = sorted(A)[::-1]
#print(A)
cnt = -1
for i in range(N-1):
  for j in range(i+1,N):
    if comb(A[i], A[j], exact=True) > cnt:
      ans = [A[i], A[j]]
      cnt = comb(A[i], A[j], exact=True)
print(*ans)

### FIXED CODE ###

import bisect
N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
#print(A)
X = A[-1]
key = bisect.bisect_left(A,A[-1] // 2)
if key + 1 == N:
  Y = key - 1
elif key - 1 == -1:
  Y = key + 1
else:
  if (A[-1] / 2) - A[key-1]  <= A[key] - (A[-1] / 2):
    Y = A[key-1]
  else:
    Y = A[key]
print(X,Y)
### BUGGY CODE ###



def get_p(ind):
    if parent[ind] != ind:
        parent[ind] = get_p(parent[ind])
    return parent[ind]



num, swap = map(int, input().split())
data = list(map(int, input().split()))

parent = [i for i in range(num + 1)]

for i in range(swap):
    a, b = map(int, input().split())
    a_parent = get_p(a)
    b_parent = get_p(b)
    if a_parent != b_parent:
        parent[max(a_parent, b_parent)] = min(a_parent, b_parent)

ans = 0

for i in range(num):
    now_int = i + 1
    ind = data.index(i + 1)
    ind += 1
    if get_p(now_int) == get_p(ind):
        ans += 1
    elif ind == now_int:
        ans += 1

print(ans)




### FIXED CODE ###



def get_p(ind):
    if parent[ind] != ind:
        parent[ind] = get_p(parent[ind])
    return parent[ind]



num, swap = map(int, input().split())
data = list(map(int, input().split()))

parent = [i for i in range(num + 1)]

for i in range(swap):
    a, b = map(int, input().split())
    a_parent = get_p(a)
    b_parent = get_p(b)
    if a_parent != b_parent:
        parent[max(a_parent, b_parent)] = min(a_parent, b_parent)

ans = 0

for i in range(num):
    now_int = i + 1
    ind =  data[i]
    if get_p(now_int) == get_p(ind):
        ans += 1
    elif ind == now_int:
        ans += 1

print(ans)
### BUGGY CODE ###

N=input()
S=input()
R=[]
G=[]
B=[]
for i in range(len(S)):
    if S[i]=='R':
        R.append(i)
    if S[i]=='G':
        G.append(i)
    if S[i]=='B':
        B.append(i)

count=0
for i in range(len(R)):
    for j in range(len(G)):

        if max(R[i],G[j])+abs(R[i]-G[j]) in B:
            count+=1

        if min(R[i],G[j])-abs(R[i]-G[j]) in B:
            count+=1

        if (R[i]+G[j])/2 in B:
            count+=1


print(str((len(R)*len(G)*len(B))-count))

### FIXED CODE ###

N=input()
S=input()
Sn=[]
R=0
G=0
B=0
for i in range(len(S)):
    if S[i]=='R':
        R+=1
        Sn.append(1)
    elif S[i]=='G':
        G+=1
        Sn.append(2)
    else:
        B+=1
        Sn.append(3)

count=0
for start in range(len(S)):
        for diff in range(1,int((len(S)-start+1)/2)):
            #int(start,diff)
            if (Sn[start]-Sn[start+diff])*(Sn[start+diff]-Sn[start+(2*diff)])*(Sn[start]-Sn[start+(2*diff)])!=0: 
                count+=1
                
print(str((R*G*B)-count))
### BUGGY CODE ###

import sys
from collections import deque

N = int(input())
A = [deque([int(i) for i in input().split()]) for i in range(N)]

ans=0
empty = [deque() for i in range(N)]
pre_fight = set([i for i in range(N)])
record = set()

while True:
    stamina=[1]*N
    for g in pre_fight:
        if A[g]!=deque():
            if g+1 == A[A[g][0]-1][0]:
                record.add(g)
                record.add(A[g][0]-1)
    if record==set():
        break
    else:
        for i in record:
            A[i].popleft()
    ans+=1
    pre_fight = record
    record = set()
    if A==empty:
        print(ans)
        sys.exit()

print(-1)

### FIXED CODE ###

import sys
from collections import deque

N = int(input())
A = [deque([int(i) for i in input().split()]) for i in range(N)]

ans=0
empty = [deque() for i in range(N)]
pre_fight = set([i for i in range(N)])
record = set()

while True:
    for g in pre_fight:
        if A[g]!=deque():
            if g+1 == A[A[g][0]-1][0]:
                record.add(g)
                record.add(A[g][0]-1)
    if record==set():
        break
    else:
        for i in record:
            A[i].popleft()
    ans+=1
    pre_fight = record
    record = set()
    if A==empty:
        print(ans)
        sys.exit()

print(-1)
### BUGGY CODE ###

from collections import deque

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

G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

ls = deque([[0, 0]])
ans = [-1] * N
depthes = [float("inf")] * N 
ans[0] = 0
depthes[0] = 0
while len(ls) > 0:
    v, depth = ls.pop()

    for next_v in G[v]:
        if depthes[next_v] < depth+1:
            continue
        ans[next_v] = v
        depthes[next_v] = depth + 1
        ls.append([next_v, depth+1])

if -1 in ans:
    print("No")
else:
    print("Yes")
    for i in range(1, N):
        print(ans[i]+1)

### FIXED CODE ###

from collections import deque

N, M = map(int, input().split())
g = [[int(i) for i in input().split()] for j in range(M)]

G = [[] for i in range(N)]
for i in range(M):
    a, b = g[i]
    G[a-1].append(b-1)
    G[b-1].append(a-1)

marks = [-1 for i in range(N)]
node = deque([[0, 0]])
while len(node) > 0:
    v = node.popleft()
    if marks[v[0]] == -1:
        marks[v[0]] = v[1]
        for i in G[v[0]]:
            if marks[i] == -1:
                node.append([i, v[0]])

if -1 not in marks:
    print("Yes")
    for i in range(1, N):
        print(marks[i]+1)
else:
    print("No")
### BUGGY CODE ###

a=int(input())
li = list(map(int,input().split()))
c = 0
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

for i in range(len(li)-1):
    if len(list(set(li))) != len(li):
        c = 1
        break
    for j in range(i+1,len(li)):
        x = make_divisors(li[i])
        y = make_divisors(li[j])
        z = x + y 
        if len(x)+len(y)-1 == len(z):
            c +=1

if c > 0:
    print('NO')
else:
    print('YES')

### FIXED CODE ###

a=int(input())
li = list(map(int,input().split()))
c = 0
if len(li) != len(set(li)):
    print('NO')
else:
    print('YES')
### BUGGY CODE ###

h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]

TS = list(zip(*S))

toUP = [[0] * w for _ in range(h)]
for i in range(w):
  cnt = 0
  for j in range(h):
    if S[j][i] == ".":
      cnt += 1
      toUP[j][i] = cnt
    else:
      cnt = 0

toDOWN = [[0] * w for _ in range(h)]
for i in range(w):
  cnt = 0
  for j in range(h - 1, -1, -1):
    if S[j][i] == ".":
      cnt += 1
      toDOWN[j][i] = cnt
    else:
      cnt = 0


toLEFT = [[0] * w for _ in range(h)]
for i in range(h):
  cnt = 0
  for j in range(w):
    if S[i][j] == ".":
      cnt += 1
      toLEFT[i][j] = cnt
    else:
      cnt = 0
    
toRIGHT = [[0] * w for _ in range(h)]
for i in range(h):
  cnt = 0
  for j in range(w - 1, -1, -1):
    if S[i][j] == ".":
      cnt += 1
      toRIGHT[i][j] = cnt
    else:
      cnt = 0

ans = 0
for i in range(h):
  for j in range(w):
    if S[i][j] == ".":
      ans = max(ans, toUP[i][j] + toDOWN[i][j] + toLEFT[i][j] + toRIGHT[i][j] - 3)
print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

# L, R, U, D方向の照らされるマス数を事前に計算
L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]

for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      L[i][j] = 0
    elif j == 0:
      L[i][j] = 1
    else:
      L[i][j] = L[i][j - 1] + 1

for i in range(H):
  for j in reversed(range(W)):
    if S[i][j] == "#":
      R[i][j] = 0
    elif j == W - 1:
      R[i][j] = 1
    else:
      R[i][j] = R[i][j + 1] + 1

for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      U[i][j] = 0
    elif i == 0:
      U[i][j] = 1
    else:
      U[i][j] = U[i - 1][j] + 1

for i in reversed(range(H)):
  for j in range(W):
    if S[i][j] == "#":
      D[i][j] = 0
    elif i == H - 1:
      D[i][j] = 1
    else:
      D[i][j] = D[i + 1][j] + 1

ans = 0
for i in range(H):
  for j in range(W):
    ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)

print(ans)
### BUGGY CODE ###

n=int(input())
a=[int(i)%(1000000000+7) for i in input().split()]
res=0
for i in range(n-1):
    for j in range(i+1,n):
        res+=(a[i]*a[j])%(1000000000+7)
print(res%(1000000000+7))

### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
s=sum(a)
mod=10**9+7
res=0
for i in a:
    s-=i
    res+=i*s%mod
print(res%mod)
### BUGGY CODE ###

N=int(input())
s_=[ ''.join(sorted(input())) for i in range(N)]
s_.sort()

ans=0
result=[]
for i in range(N):
    s=s_[i]
    ans+=result.count(s)
    result.append(s)
print(ans)

### FIXED CODE ###

import collections as cl
import math
N=int(input())

result_=[]
for i in range(N):
    s= ''.join(sorted(input()))
    result_.append(s)

result=list(cl.Counter(result_).values())

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans=0
for j in range(len(result)):
    if result[j]==1:
        continue
    else:
        ans+=combinations_count(result[j],2)

print(ans)
### BUGGY CODE ###

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

cards = range(1, N+1)
for _ in range(M):
    l, r = map(int, input().split())
    cards = set(cards) & set(range(l, r+1))
print(len(cards))

### FIXED CODE ###

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

L, R = [], []
for _ in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
diff = min(R) - max(L) + 1
if diff > 0:
    print(diff)
else:
    print(0)
### BUGGY CODE ###

import sys

N = int(input())
p = list(map(int, input().split()))

product = 1
for i in range(N):
    product = product * p[i]

if product > 10 ** 18:
    print(-1)
    sys.exit()
print(product)

### FIXED CODE ###

import sys

N = int(input())
p = list(map(int, input().split()))


for i in range(N):
    if p[i] == 0:
        print(0)
        sys.exit()

product = 1
for i in range(N):
    product = product * p[i]
    if product > 10 ** 18:
        print(-1)
        sys.exit()
        break

print(product)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = []
while len(A) > 1:
    a = A[0]
    B = []
    if a != A[1]:
        ans.append(a)
    for aa in A:
        if aa % a != 0:
            B.append(aa)
    A = B
if len(A) == 1:
    print(len(ans)+1)
else:
    print(len(ans))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = set()
C = set()
for a in A:
    if a in B:
        C.add(a)
    else:
        B.add(a)
M = max(B)
bool = [1]*(M+1)
for c in C:
    bool[c] = 0
for b in B:
    for i in range(b*2, M+1, b):
        bool[i] = 0
ans = 0
for a in A:
    if bool[a] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
east_side = list(input())
west_side = []
ans = []
for i in range(len(east_side)):
    WE_sum = east_side.count("E") + west_side.count("W")
    ans.append(WE_sum)
    west_side.append(east_side[0])
    east_side.pop(0)
print(min(ans))


### FIXED CODE ###

n = int(input())
s = input()
rev_counter = []
rev_num = s.count("E")
if s[0] == "E":
    rev_num -= 1
rev_counter.append(rev_num)
for i in range(1, n):
    if s[i] == "E" and s[i-1] == "E":
        rev_num -= 1
    elif s[i] == "W" and s[i-1] == "W":
         rev_num += 1
    rev_counter.append(rev_num)
print(min(rev_counter))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,M=map(int,input().split())
A=list(map(int,input().split()))

need =[2,5,5,4,5,6,3,7,6]

dp = [[0]*(N+1) for _ in range(M)]
dpmax = [0]*(N+1)

for j in range(2,N+1):
  tmpmax = 0
  for i in range(M):
    tmp = need[A[i]-1]
    if j == tmp:
      dp[i][j] = A[i]
    elif j > tmp:
      if dpmax[j-tmp] != 0:
        tmp2 = dpmax[j-tmp]
        dp[i][j] = max(A[i]*(10**len(str(tmp2)) + tmp2,tmp2*10+A[i]))
    if tmpmax < dp[i][j]:
      tmpmax = dp[i][j]
  dpmax[j] = tmpmax
  
print(dpmax[-1])

### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))

if N % 2 == 0:
  if 1 in A:
    print(int('1'*(N//2)))
    exit()

need =(2,5,5,4,5,6,3,7,6)

if 2 in A and 3 in A:
  del A[A.index(2)]
if 3 in A and 5 in A:
  del A[A.index(3)]
if 6 in A and 9 in A:
  del A[A.index(6)]
if 1 in A and 4 in A:
  del A[A.index(4)]
if 6 in A and 7 in A:
  del A[A.index(6)] 
if 7 in A and 9 in A:
  del A[A.index(9)] 
if 1 in A and 6 in A:
  del A[A.index(6)] 
if 1 in A and 9 in A:
  del A[A.index(9)] 
  
A = tuple(A)
M = len(A)

dp = [[0]*(N+1) for _ in range(M)]
dpmax = [0]*(N+1)

def take_max():
  return max(A[i]*(10**len(str(tmp2)) + tmp2,tmp2*10+A[i]))

for j in range(2,N+1):
  tmpmax = 0
  for i in range(M):
    tmp = need[A[i]-1]
    if j == tmp:
      dp[i][j] = A[i]
    elif j > tmp:
      if dpmax[j-tmp] != 0:
        tmp2 = dpmax[j-tmp]
        dp[i][j] = take_max()
    if tmpmax < dp[i][j]:
      tmpmax = dp[i][j]
  dpmax[j] = tmpmax
  
print(dpmax[-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C


if __name__ == '__main__':
    spot_count = int(input())
    mod_spots = [0] + list(map(int, input().split())) + [0]

    # FIXME: TLE
    for i in range(spot_count):
        tmp = mod_spots[i + 1]
        if mod_spots[i] <= mod_spots[i + 2]:
            mod_spots[i + 1] = mod_spots[i]
        elif (mod_spots[i] > 0) and mod_spots[i + 2] > 0:
            mod_spots[i + 1] = 0
        else:
            mod_spots[i + 1] = mod_spots[i]

        cost = sum([abs(mod_spots[j + 1] - mod_spots[j]) for j in range(spot_count + 1)])
        mod_spots[i + 1] = tmp
        print(cost)


### FIXED CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    spot_count = int(input())
    spots = [0] + list(map(int, input().split())) + [0]

    # See:
    # https://www.youtube.com/watch?v=WFg2yJGZ2Cw
    # https://img.atcoder.jp/arc093/editorial.pdf
    total_distance = 0
    total_cost = 0

    for i in range(spot_count + 1):
        total_distance += abs(spots[i + 1] - spots[i])

    for j in range(1, spot_count + 1):
        shortcut_cost = (abs(spots[j - 1] - spots[j]) + abs(spots[j] - spots[j + 1]))
        total_cost = total_distance + abs(spots[j - 1] - spots[j + 1]) - shortcut_cost
        print(total_cost)
### BUGGY CODE ###

import itertools
while 1:
	try:
		n = input()
		if n == 0: break
		s = sorted(map(int,raw_input().split()))
		sm = sum(s)
		for i in range(1,n-1):
			ans = sorted(abs(sm - 2*sum(party)) for party in itertools.combinations(s,i))[0]
			if ans == 0: break
		print ans
	except:
		pass

### FIXED CODE ###

def S(i,x,y):
	if 2*x >= A: return 2*x-A
	if 2*y >= A: return 2*y-A
	return min(S(i+1,x+a[i],y),S(i+1,x,y+a[i]))
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))[::-1]
	A = sum(a)
	print S(1,a[0],0)