CodeEff/ECCO huggingface dataset:
# Original solution
#!/usr/bin/env python

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

mod = int(1e9)+7

total = sum(a)
ans = 0 
for i in range(n):
    ans += (a[i]*(total-a[i]))%mod
    total -= a[i]

print((ans%mod))


# Optimized solution
#!/usr/bin/env python

n = int(eval(input()))
a = list(map(int, input().split()))
mod = int(1e9)+7

s = sum(a)
ans = sub = 0 
for i in range(n):
    ans += a[i]*s
for i in range(n):
    sub += a[i]*a[i]
ans = ((ans-sub)//2)%mod
print(ans)
# Original solution
ans = 0
N = int(eval(input()))
array = list(map(int, input().split()))
for i in range(N):
      ans += array[i]*sum(array[i+1:N])
print((ans%(10**9+7)))

# Optimized solution
ans = 0
N = int(eval(input()))
array = list(map(int, input().split()))
x = sum(array)
y = 0
for i in range(N):
  y += array[i]**2

ans = x**2 -y
print(((ans//2)%(10**9+7)))
# Original solution
ans = 0
N = int(eval(input()))
array = list(map(int, input().split()))
x = sum(array)
y = 0
for i in range(N):
  y += array[i]**2

ans = x**2 -y
print(((ans//2)%(10**9+7)))

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
 
ans = 0
x = sum(A)
 
for i in range(N - 1):
    x -= A[i]
    ans += A[i] * x
    
ans = ans % (10 ** 9 + 7)
 
print(ans)
# Original solution
import itertools

n=int(eval(input()))
l=list(map(int,input().split()))

mod = 10**9 + 7

ans=0
for i,j in itertools.combinations(l, 2):
  num=i*j
  ans+=num
  
print((ans%mod))


# Optimized solution
n=int(eval(input()))
l=list(map(int,input().split()))

sum_l=sum(l)
ans=0
mod=10**9+7

for i in range(n):
  sum_l-=l[i]
  ans+=l[i]*sum_l
  
print((ans%mod))
# Original solution
L,A,B,M = list(map(int,input().split()))

def si(i):
  return A + B * i

s = [str(si(i)) for i in range(L)]

n = ""
for i in s:
  n += i
n = int(n)

print((n % M))

# Optimized solution
L,A,B,M = list(map(int,input().split()))

def si(i):
  return A + B * i

n = ""
for i in range(L):
  n += str(si(i))
n = int(n)

print((n % M))
# Original solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from functools import lru_cache

L,A,B,MOD = list(map(int,read().split()))

@lru_cache(None)
def F(r,n,MOD):
    # 1+r+...+r^{n-1} をダブリングで求める
    if n == 0:
        return 0
    q = n//2
    x = F(r,q,MOD)
    # 1+r^qをかける
    x *= 1 + pow(r,q,MOD); x %= MOD
    if n&1:
        x *= r; x += 1; x %= MOD
    return x

@lru_cache(None)
def G(r,n,MOD):
    # sum ir^i をダブリングで求める
    if n == 0:
        return 0
    q = n//2
    x = G(r,q,MOD)
    # 1+r^qをかける
    x *= 1 + pow(r,q,MOD); x %= MOD
    # q(r^q+...+r^{2q-1})を加える
    x += F(r,q,MOD) * pow(r,q,MOD) * q % MOD
    if n&1:
        x *= r; x += F(r,n,MOD); x -= 1; x %= MOD
    return x

S = 0
for d in range(1,20):
    # d桁の最初、最後、項数
    lower = 10**(d-1)
    upper = 10**d-1
    # lower <= A+nB <= upper
    nlower = (lower-A+B-1)//B
    nupper = (upper-A)//B
    if nlower < 0:
        nlower = 0
    if nupper >=L:
        nupper = L-1
    if nlower > nupper:
        continue
    items = nupper - nlower + 1
    r = (10**d) % MOD
    last = A+B*nupper
    x = last * F(r,items,MOD)
    x -= B * G(r,items,MOD)
    length = d*items
    S *= pow(10,length,MOD); S += x
    S %= MOD

print(S)



# Optimized solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

L,A,B,MOD = list(map(int,read().split()))

def geom_seq_sum(r,n,MOD):
    """
    return \sum_{i=0}^{n-1} r^i mod MOD
    """
    if r == 1:
        return n%MOD
    r1 = r-1
    return ((pow(r,n,r1*MOD)-1)//r1)% MOD

def geom_seq_sum_1(r,n,MOD):
    """
    return \sum_{i=0}^{n-1} ir^i mod MOD
    """
    if r == 1:
        return n*(n-1)//2%MOD
    r1 = r-1
    x = pow(r,n,r1*r1*MOD)
    return (-(x-1)//r1 + (n-1)*x + 1)//r1 % MOD

S = 0
for d in range(1,20):
    # d桁の最初、最後、項数
    lower = 10**(d-1)
    upper = 10**d-1
    # lower <= A+nB <= upper
    nlower = (lower-A+B-1)//B
    nupper = (upper-A)//B
    if nlower < 0:
        nlower = 0
    if nupper >=L:
        nupper = L-1
    if nlower > nupper:
        continue
    items = nupper - nlower + 1
    r = (10**d) % MOD
    last = A+B*nupper
    x = last * geom_seq_sum(r,items,MOD)
    x -= B * geom_seq_sum_1(r,items,MOD)
    length = d*items
    S *= pow(10,length,MOD); S += x
    S %= MOD

print(S)
# Original solution
from math import ceil
def dot(a,b,m):
    c = [[0,0,0],[0,0,0],[0,0,0]]
    for i in range(3):
        for j in range(3):
            for k in range(3):
                c[i][j] += a[i][k]*b[k][j]
                c[i][j] %= m
    return c
def powm(a,n,m):
    if n == 0:
        return [[1,0,0],[0,1,0],[0,0,1]]
    for i in range(3):
        for j in range(3):
            a[i][j] %= m
    if n%2==0:
        return dot(powm(a,n//2,m),powm(a,n//2,m),m)
    else:
        return dot(dot(powm(a,n//2,m),powm(a,n//2,m),m),a,m)

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

a = [[1,0,0],[0,1,0],[0,0,1]]
for d in range(1,19):
    C = min(max(0,ceil((10**d-A)/B)),L)-min(max(0,ceil((10**(d-1)-A)/B)),L)
    a = dot(powm([[pow(10,d,M),1,0],[0,1,B%M],[0,0,1]],C,M),a,M)
ans = (a[0][1]*A+a[0][2])%M
print(ans)

# Optimized solution
def dot(a,b,m):
    c = [[0,0,0],[0,0,0],[0,0,0]]
    for i in range(3):
        for j in range(3):
            for k in range(3):
                c[i][j] += a[i][k]*b[k][j]
                c[i][j] %= m
    return c
    
def powm(a,n,m):
    if n == 0:
        return [[1,0,0],[0,1,0],[0,0,1]]
    for i in range(3):
        for j in range(3):
            a[i][j] %= m
    r = powm(a,n//2,m)
    if n%2==0:
        return dot(r,r,m)
    else:
        return dot(dot(r,r,m),a,m)

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

a = [[1,0,0],[0,1,0],[0,0,1]]
for d in range(1,19):
    C = min(max(0,(10**d-A-1)//B+1),L)-min(max(0,(10**(d-1)-A-1)//B+1),L)
    a = dot(powm([[pow(10,d,M),1,0],[0,1,B%M],[0,0,1]],C,M),a,M)
ans = (a[0][1]*A%M+a[0][2])%M
print(ans)
# Original solution
L, A, B, M = list(map(int, input().split()))

ten = 1

def f(l):
  if l == 0:
    return 0
  if l % 2 == 1:
    pl = l - 1
    x = f(pl)
    return (x * ten + 1) % M
  else:
    pl = l // 2
    x = f(pl)
    return (x * ten ** pl + x) % M

def g(l):
  if l == 0:
    return 0
  if l % 2 == 1:
    pl = l - 1
    x = g(pl)
    return (x * ten + B * pl) % M
  else:
    pl = l // 2
    x = g(pl)
    return (x * ten ** pl + x + B * pl * f(pl)) % M

last = A + B * (L - 1)
ans = 0

for i in range(1, 19):
  l = ten
  r = ten * 10 - 1
  
  if last < l:
    ten *= 10
    continue
  if A > r:
    ten *= 10
    continue
  na = 0 #初項
  nl = 0 #長さ

  if A >= l:
    na = A
  else:
    na = (l - A + B - 1) // B * B + A
    na = min(na, last)
  
  nlast = 0
  if last <= r:
    nlast = last
  else:
    nlast = (r - A) // B * B + A
  nl = (nlast - na) // B + 1

  ten *= 10
  ans *= ten ** nl % M
  ans += (na * f(nl)) % M
  ans += g(nl) % M

print((ans % M))

# Optimized solution
L, A, B, M = list(map(int, input().split()))

ten = 0

def pow_(x, t):
  if t == 0:
    return 1
  if t % 2 == 1:
    return (pow_(x, t - 1) * x) % M
  else:
    y = pow_(x, t // 2)
    return (y * y) % M

def f(l):
  if l == 0:
    return 0
  if l % 2 == 1:
    pl = l - 1
    x = f(pl)
    return x * ten + 1
  else:
    pl = l // 2
    x = f(pl)
    return x * pow_(ten, pl) + x

def g(l):
  if l == 0:
    return 0
  if l % 2 == 1:
    pl = l - 1
    x = g(pl)
    return x * ten + B * pl
  else:
    pl = l // 2
    x = g(pl)
    return x * pow_(ten, pl) + x + B * pl * f(pl)

last = A + B * (L - 1)
ans = 0
ten = 10
for _ in range(18):
  l = ten // 10
  r = ten - 1
  
  if last < l:
    ten *= 10
    continue
  if A > r:
    ten *= 10
    continue
  na = 0 #初項
  nl = 0 #長さ

  if A >= l:
    na = A
  else:
    na = (l - A + B - 1) // B * B + A
    na = min(na, last)
  
  nlast = 0
  if last <= r:
    nlast = last
  else:
    nlast = (r - A) // B * B + A
  nl = (nlast - na) // B + 1

  ans *= pow_(ten, nl) % M
  ans += (na * f(nl)) % M
  ans += g(nl) % M
  ten *= 10

print((ans % M))
# Original solution
import sys
sys.setrecursionlimit(100000000)

def mult(A, B, mod): #行列A, Bの内積を求める。
    D = [[(A[0][0] * B[0][0]) % mod, 0, 0], [0, 1, 0], [0, 0, 1]]
    D[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % mod
    D[2][0] = (A[2][0]*B[0][0]+A[2][1]*B[1][0]+A[2][2]*B[2][0]) % mod
    D[2][1] = (A[2][1]*B[1][1]+A[2][2]*B[2][1]) % mod
    return D

def double(C, mod):
    D = [[pow(C[0][0], 2, mod), 0, 0], [(C[1][0] * C[0][0] + C[1][0]) % mod, 1, 0], [(C[2][0] * C[0][0] + C[2][1] * C[1][0] + C[2][0]) % mod, (C[2][1] * 2) % mod, 1]]
    return D

def Cpow(C, n, mod):
    if n == 1: return C
    else:
        D = double(C, mod)
        if n % 2 == 0:
            return Cpow(D, n // 2, mod)
        else:
            return mult(Cpow(D, n // 2, mod), C, mod)

def solve():
    L, a, b, M = list(map(int, input().split()))
    X = 0
    s = a
    nd = -1
    ne = 0
    for d in range(1, 19):
        ne = min((pow(10, d) - a - 1) // b, L-1)
        if ne == nd: continue
        C = [[pow(10, d, M), 0, 0], [1, 1, 0], [0, b % M, 1]]
        D = Cpow(C, ne - nd, M)
        X = (X * D[0][0] + D[1][0] * s + D[2][0]) % M
        s += D[2][1]
        if ne == L - 1: break
        nd = ne
    print(X)
    return

if __name__ == "__main__":
    solve()

# Optimized solution
import sys
sys.setrecursionlimit(100000000)

def mult(A, B, mod): #行列A, Bの内積を求める。
    D = [[(A[0][0] * B[0][0]) % mod, 0, 0], [0, 1, 0], [0, 0, 1]]
    D[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % mod
    D[2][0] = (A[2][0]*B[0][0]+A[2][1]*B[1][0]+A[2][2]*B[2][0]) % mod
    D[2][1] = (A[2][1]*B[1][1]+A[2][2]*B[2][1]) % mod
    return D

def double(C, mod):
    D = [[pow(C[0][0], 2, mod), 0, 0], [(C[1][0] * C[0][0] + C[1][0]) % mod, 1, 0], [(C[2][0] * C[0][0] + C[2][1] * C[1][0] + C[2][0]) % mod, (C[2][1] * 2) % mod, 1]]
    return D

def Cpow(C, n, mod):
    if n == 1: return C
    else:
        D = double(C, mod)
        if n % 2 == 0:
            return Cpow(D, n // 2, mod)
        else:
            return mult(Cpow(D, n // 2, mod), C, mod)

def solve():
    L, a, b, M = list(map(int, input().split()))
    X = 0
    s = a
    nd = -1
    ne = 0
    for d in range(1, 19):
        ne = min((pow(10, d) - a - 1) // b, L-1)
        if ne < 0: continue
        elif ne == nd: continue
        C = [[pow(10, d, M), 0, 0], [1, 1, 0], [0, b % M, 1]]
        D = Cpow(C, ne - nd, M)
        X = (X * D[0][0] + D[1][0] * s + D[2][0]) % M
        s += D[2][1]
        if ne == L - 1: break
        nd = ne
    print(X)
    return

if __name__ == "__main__":
    solve()
# Original solution
L, A, B, M = list(map(int, input().split()))
numstrlist = list(map(str, list(range(A, A+B*L, B))))
numstr = "".join(numstrlist)
numlist = list(numstr)
length = len(numlist)-1
ans = 0
for i, c in enumerate(numlist):
    ans += int(c)
    if i != length:
        ans = ans * 10 % M
print(ans)

# Optimized solution
L, A, B, M = list(map(int, input().split()))
l_i = 0
s = A
ans = 0
while l_i != L:
    numlist = list(str(s))
    for i, c in enumerate(numlist):
        ans += int(c)
        if i != len(numlist)-1 or l_i != L-1:
            ans = ans * 10 % M
    s += B
    l_i += 1
print(ans)
# Original solution
#F - Takahashi's Basics in Education and Learning
L,A,B,M=(int(i) for i in input().split())
tmp=[A+B*i for i in range(L)]
result=""
for i in range(L):
    result+=str(tmp[i])
print((int(result)%M))

# Optimized solution
L,A,B,M=(int(i) for i in input().split())
result=""
for i in range(L):
    result+=str(A+B*i)
print((int(result)%M))
# Original solution
L,A,B,mod=list(map(int,input().split()))
def f(l):
  return max(0,(10**l-A-1)//B+1)

def m(a,b):
  r=[[0]*len(b[0]) for i in range(len(a))]
  for i in range(len(a)):
    for k in range(len(b)):
      for j in range(len(b[0])):
        r[i][j]=(r[i][j]+a[i][k]*b[k][j])%mod
  return r

def p(a,n):
  r=[[0]*len(a) for i in range(len(a))]
  b=[]
  for i in range(len(a)):
    r[i][i]=1
    b.append(a[i][:])
  l=n
  while l>0:
    if l&1:
      r=m(b,r)
    b=m(b,b)
    l>>=1
  return r

'''
100   001
B10 * 00s
01l   00P
'''

X=[[0,0,1],[0,0,A],[0,0,0]]
Y,R,Z=0,1,0
while L:
  Y=[[1,0,0],[B,1,0],[0,1,pow(10,R,mod)]]
  Z=min(L,f(R)-f(R-1))
  L-=Z
  Y=p(Y,Z)
  X=m(Y,X)
  R+=1
print((X[2][2]%mod))

# Optimized solution
L,A,B,mod=list(map(int,input().split()))
def f(l):
  return max(0,(10**l-A-1)//B+1)

def m(a,b):
  r=[[0]*len(b[0]) for i in range(len(a))]
  for i in range(len(a)):
    for k in range(len(b)):
      for j in range(len(b[0])):
        r[i][j]=(r[i][j]+a[i][k]*b[k][j])%mod
  return r

def p(a,n):
  r=[[0]*len(a) for i in range(len(a))]
  b=[]
  for i in range(len(a)):
    r[i][i]=1
    b.append(a[i][:])
  l=n
  while l>0:
    if l&1:
      r=m(b,r)
    b=m(b,b)
    l>>=1
  return r

X=[[0,0,1],[0,0,A],[0,0,0]]
Y,R,Z=0,1,0
while L:
  Y=[[1,0,0],[B,1,0],[0,1,pow(10,R,mod)]]
  Z=min(L,f(R)-f(R-1))
  L-=Z
  Y=p(Y,Z)
  X=m(Y,X)
  R+=1
print((X[2][2]%mod))
# Original solution
l, a, b, m = list(map(int, input().split()))

print((int(''.join(list(map(str, [a+b*i for i in range(l)]))))%m))

# Optimized solution
l, a, b, m = list(map(int, input().split()))

num = []
for i in range(l):
    num.append(str(a + i * b))
    
print((int(''.join(num))%m))
# Original solution
s = [len(x) for x in input().split('T')]
x, y = list(map(int, input().split()))
len_s = len(s)
sx = [s[i] for i in range(len_s) if i % 2 == 0]
sy = [s[i] for i in range(len_s) if i % 2 == 1]

x -= sx[0]
sx = sx[1:]



def is_reachable(p, s):
    origin = 8000
    if origin+p < 0:
        return False
        
    n = len(s)
    reachable = [[False for _ in range(origin * 2 + 1)] for i in range(n + 2)]
    reachable[0][origin] = True

    for i in range(n):
        for j in range(origin * 2 + 1):
            if not reachable[i][j]:
                continue
            if j - s[i] >= 0:
                reachable[i + 1][j - s[i]] = True
            if j + s[i] <= origin * 2:
                reachable[i + 1][j + s[i]] = True
    return reachable[n][p + origin] or reachable[n][-p + origin]


if is_reachable(x, sx) and is_reachable(y, sy):
    print('Yes')
else:
    print('No')


# Optimized solution
s = [len(x) for x in input().split('T')]
x, y = list(map(int, input().split()))
len_s = len(s)
sx = [s[i] for i in range(len_s) if i % 2 == 0]
sy = [s[i] for i in range(len_s) if i % 2 == 1]

x -= sx[0]
sx = sx[1:]



def is_reachable(p, s):
    origin = 8000
    if origin+p < 0:
        return False
        
    n = len(s)
    reachable = [set() for i in range(n + 1)]
    reachable[0].add(origin)

    for i in range(n):
        for j in list(reachable[i]):
            if j - s[i] >= 0:
                reachable[i + 1].add(j - s[i])
            if j + s[i] <= origin * 2:
                reachable[i+1].add(j + s[i])
    return (origin+p) in reachable[n] or (origin-p) in reachable[n]


if is_reachable(x, sx) and is_reachable(y, sy):
    print('Yes')
else:
    print('No')
# Original solution
s = input().split("T")
x,y = list(map(int,input().split()))
xmove = []
ymove = []
for i in range(1,len(s)):
    if i % 2 == 0:
        xmove.append(s[i].count("F"))
    else:
        ymove.append(s[i].count("F"))
dpx = [[False]*(16001) for i in range(len(xmove)+1)]
dpy = [[False]*(16001) for i in range(len(ymove)+1)]
dpx[0][s[0].count("F")+8000] = True
dpy[0][8000] = True
for i in range(len(xmove)):
    for j in range(16001):
        if dpx[i][j]:
            if 0<=j-xmove[i]:
                dpx[i+1][j-xmove[i]] = True
            if j+xmove[i] <= 16001:
                dpx[i+1][j+xmove[i]] = True
for i in range(len(ymove)):
    for j in range(16001):
        if dpy[i][j]:
            if 0<=j-ymove[i]:
                dpy[i+1][j-ymove[i]] = True
            if j+ymove[i] <= 16001:
                dpy[i+1][j+ymove[i]] = True

if dpx[len(xmove)][x+8000] and dpy[len(ymove)][y+8000]:
    print("Yes")
else:
    print("No")

# Optimized solution
s = input().split("T")
x,y = list(map(int,input().split()))
xmove = []
ymove = []
for i in range(len(s)):
    if i % 2 == 1:
        ymove.append(s[i].count("F"))
    else:
        xmove.append(s[i].count("F"))
#リストで持つdpだとTLEしたのでメモ化再帰で書く

def solve(l,cor):
    dp = {0}
    for c in l:
        dp = {c+i for i in dp}|{i-c for i in dp}
    return cor in dp

if solve(xmove[1:],x-xmove[0]) and solve(ymove,y):
    print("Yes")
else:
    print("No")
# Original solution
s = input().split('T')
x, y = list(map(int, input().split()))
x = abs(x-len(s[0]))
y = abs(y)
dx = []
for i in range(2, len(s), 2) :
    dx.append(len(s[i]))
dy = []
for i in range(1, len(s), 2) :
    dy.append(len(s[i]))

if sum(dx) < x or sum(dy) < y :
    print('No')
    exit()

xl = len(dx)
for i in range(1 << xl) :
    nx = 0
    for j in range(xl) :
        if i>>j & 1 :
            nx -= dx[j]
        else :
            nx += dx[j]
    if nx == x :
        break
else :
    print('No')
    exit()

yl = len(dy)
for i in range(1 << yl) :
    ny = 0
    for j in range(yl) :
        if i>>j & 1 :
            ny -= dy[j]
        else :
            ny += dy[j]
    if ny == y :
        break
else :
    print('No')
    exit()

print('Yes')

# Optimized solution
s = input().split('T')
x, y = list(map(int, input().split()))
s = [len(_) for _ in s]
dx = s[::2]
dy = s[1::2]

x = abs(x-dx[0])
y = abs(y)
dx = dx[1:]
px = 0
py = 0
for d in reversed(sorted(dx)) :
    if px > x :
        px -= d
    else :
        px += d

for d in reversed(sorted(dy)) :
    if py > y :
        py -= d
    else :
        py += d

if px == x and py == y :
    print('Yes')
else :
    print('No')
# Original solution
N = int(eval(input()))
a = list(map(int, input().split()))

l = sorted(a[:N])
r = sorted(a[N:])

lsum = sum(l)
rsum = sum(r[:N])

import bisect

ans = lsum - rsum
for i in range(N):
    c = a[N+i]
    li = bisect.bisect_left(l, c)
    ri = bisect.bisect_left(r, c)
    if li > 0: 
        lsum = lsum + c - l[0]
        l.insert(li, c)
        del l[0]
    if ri < N:
        rsum = rsum - c + r[N]
    del r[ri]
    ans = max(ans, lsum - rsum)

print(ans)

# Optimized solution
N = int(eval(input()))
a = list(map(int, input().split()))
 
import heapq

left = [0]*(N+1)
l = a[:N]
left[0] = sum(l)

heapq.heapify(l)
for i in range(1, N+1):
    c = a[N+i-1]    
    lmin = heapq.heappop(l)
    if lmin < c:
        left[i] = left[i-1] + c - lmin
        heapq.heappush(l, c)
    else:
        left[i] = left[i-1]
        heapq.heappush(l, lmin)

a = [-x for x in a[::-1]]
right = [0]*(N+1)
r = a[:N]
right[0] = sum(r)

heapq.heapify(r)
for i in range(1, N+1):
    c = -a[N+i-1]    
    rmax = -heapq.heappop(r)
    if rmax > c:
        right[i] = right[i-1] - c + rmax
        heapq.heappush(r, -c)
    else:
        right[i] = right[i-1]
        heapq.heappush(r, -rmax)

ans = -10**20
for i in range(N+1):
    ans = max(ans, left[i] + right[N-i])

print(ans)
# Original solution
import heapq
n=int(eval(input()))
a=list(map(int,input().split()))
q=a[0:n]
sums=[0]*(n+1)
sums[0]=sum(q)
heapq.heapify(q)
am=a[n:2*n]
for i in range(0,n):
    heapq.heappush(q,am[i])
    heapq.heappop(q)
    sums[i+1]=sum(q)
p=a[2*n:3*n]
p=list([x*(-1) for x in p])
sums[n]+=sum(p)
heapq.heapify(p)
for i in range(n-1,-1,-1):
    heapq.heappush(p,(-1)*am[i])
    heapq.heappop(p)
    sums[i]+=sum(p)
print((max(sums)))

# Optimized solution
import heapq
n=int(eval(input()))
a=list(map(int,input().split()))
q=a[0:n]
sums=[0]*(n+1)
sums[0]=sum(q)
heapq.heapify(q)
am=a[n:2*n]
for i in range(0,n):
    heapq.heappush(q,am[i])
    sums[i+1]=sums[i]+am[i]-heapq.heappop(q)
p=a[2*n:3*n]
p=list([x*(-1) for x in p])
sump=sum(p)
sums[n]+=sump
heapq.heapify(p)
for i in range(n-1,-1,-1):
    heapq.heappush(p,(-1)*am[i])
    sump=sump-am[i]-heapq.heappop(p)
    sums[i]+=sump
print((max(sums)))
# Original solution
from heapq import heappop, heappush
N = int(eval(input()))
a = list(map(int, input().split()))

pq1 = []
for x in a[:N]:
    heappush(pq1, x)

pq2 = sorted(a[N:])

ans = sum(pq1) - sum(pq2[:N])
for k in range(N, 2 * N):
    heappush(pq1, a[k])
    heappop(pq1)    
    pq2.remove(a[k])
    
    ans = max(ans, sum(pq1) - sum(pq2[:N]))
    
print(ans)


# Optimized solution
from heapq import heappop, heappush, heapify
N = int(eval(input()))
a = list(map(int, input().split()))

pq1 = a[:N]
pq2 = [-x for x in a[2 * N:]]

heapify(pq1)
heapify(pq2)

s1 = sum(pq1)
s2 = sum(pq2)

ans1 = [s1]
ans2 = [s2]

for k in range(N, 2 * N):
    heappush(pq1, a[k])
    x = heappop(pq1)
    s1 += a[k] - x
    ans1.append(s1)
    
    heappush(pq2, -a[3 * N - k - 1])
    x = heappop(pq2)
    s2 += -a[3 * N - k - 1] - x
    ans2.append(s2)
    
print((max(ans1[i] + ans2[-i - 1] for i in range(len(ans1)))))
# Original solution
import heapq
n=int(eval(input()))
a=list(map(int,input().split()))
ans=[0 for i in range(n+1)]
ans[0]=sum(a[:n])
b=a[:n]
heapq.heapify(b)
for i in range(n):
  c=heapq.heappop(b)
  if c>a[n+i]:
    heapq.heappush(b,c)
    ans[i+1]=sum(b)
  else:
    heapq.heappush(b,a[n+i])
    ans[i+1]=sum(b)
b=a[2*n:]
for i in range(n):
  b[i]=-b[i]
heapq.heapify(b)
ans[n]+=sum(b)
for i in range(n-1,-1,-1):
  c=heapq.heappop(b)
  if c>-a[n+i]:
    heapq.heappush(b,c)
    ans[i]+=sum(b)
  else:
    heapq.heappush(b,-a[n+i])
    ans[i]+=sum(b)
print((max(ans)))

# Optimized solution
import heapq
n=int(eval(input()))
a=list(map(int,input().split()))
ans=[0 for i in range(n+1)]
ans[0]=sum(a[:n])
b=a[:n]
heapq.heapify(b)
sb=sum(b)
for i in range(n):
  sb+=a[n+i]
  c=heapq.heappushpop(b,a[n+i])
  sb-=c
  ans[i+1]=sb
b=a[2*n:]
for i in range(n):
  b[i]=-b[i]
heapq.heapify(b)
ans[n]+=sum(b)
sb=sum(b)
for i in range(n-1,-1,-1):
  sb-=a[n+i]
  c=heapq.heappushpop(b,-a[n+i])
  sb-=c
  ans[i]+=sb
print((max(ans)))
# Original solution
# coding: utf-8

import bisect


def calc_l_score(N, a):
    scores = [None] * (N + 1)
    queue = sorted(a[:N])
    scores[0] = sum(queue)
    for i in range(N):
        na = a[N + i]
        bisect.insort(queue, na)
        m = queue.pop(0)
        scores[i + 1] = scores[i] + na - m
    return scores


def calc_r_score(N, a):
    scores = [None] * (N + 1)
    queue = sorted(a[2 * N:])
    scores[-1] = sum(queue)
    for i in range(1, N + 1):
        na = a[-N - i]
        bisect.insort(queue, na)
        m = queue.pop(-1)
        scores[-i - 1] = scores[-i] + na - m
    return scores


def main():
    N = int(eval(input()))
    a = list(map(int, input().split()))

    ls = calc_l_score(N, a)
    rs = calc_r_score(N, a)
    return max([l - r for l, r in zip(ls, rs)])


if __name__ == "__main__":
    print((main()))


# Optimized solution
# coding: utf-8

import heapq


def calc_l_score(N, a):
    scores = [None] * (N + 1)
    queue = a[:N]
    heapq.heapify(queue)
    scores[0] = sum(queue)
    for i in range(N):
        na = a[N + i]
        heapq.heappush(queue, na)
        m = heapq.heappop(queue)
        scores[i + 1] = scores[i] + na - m
    return scores


def calc_r_score(N, a):
    scores = [None] * (N + 1)
    queue = []
    for i in range(1, N + 1):
        heapq.heappush(queue, -a[-i])
    scores[-1] = - sum(queue)
    for i in range(1, N + 1):
        na = a[-N - i]
        heapq.heappush(queue, -na)
        m = - heapq.heappop(queue)
        scores[-i - 1] = scores[-i] + na - m
    return scores


def main():
    N = int(eval(input()))
    a = list(map(int, input().split()))

    ls = calc_l_score(N, a)
    rs = calc_r_score(N, a)
    return max([l - r for l, r in zip(ls, rs)])


if __name__ == "__main__":
    print((main()))