CodeEff/ECCO huggingface dataset:
# Original solution
with open(0) as f:
    N, *a = list(map(int, f.read().split()))
F = [x for x in a[:N]] #Fの要素は加えるか取り除くかの2択
C = [x for x in a[N:2*N]] 
B = [-x for x in a[2*N:]] #Bの要素は引くか取り除くかの二択
import heapq as hq
hq.heapify(F)
hq.heapify(B)

#Cを二分し、前半はFと、後半はBとで演算を行う
#演算方法(c in C)
#前半：cがF[0]より大きければF[0]を取り除くN個の一つとし、cをスコアに加える
#後半：-cがB[0]より大きければB[0]を取り除くN個の一つとし、cをスコアから引く
#どちらも場合も条件を満たさない場合はそのｃを取り除くN個の一つとする
#計算量：O(N*N*logN)
#途中計算をメモして計算量軽減
from copy import deepcopy
memoF = [[]] * (N+1) #C[:i]を前半としたときのFとの演算結果
memoF[0] = deepcopy(F)
memoB = [[]] * (N+1) #C[i:]を後半としたときのBとの演算結果
memoB[N] = deepcopy(B)
for i in range(N):
    if C[i] > F[0]:
        hq.heapreplace(F, C[i])
    if -C[N-1-i] > B[0]:
        hq.heapreplace(B, -C[N-1-i])
    memoF[i+1] = deepcopy(F)
    memoB[N-1-i] = deepcopy(B)

Scores = [sum(memoF[i])+sum(memoB[i]) for i in range(N+1)]
ans = max(Scores)
print(ans)

# Optimized solution
with open(0) as f:
    N, *a = list(map(int, f.read().split()))
F = [x for x in a[:N]] #Fの要素は加えるか取り除くかの2択
C = [x for x in a[N:2*N]] 
B = [-x for x in a[2*N:]] #Bの要素は引くか取り除くかの二択
import heapq as hq
#ヒープにして常に最小値を追跡
hq.heapify(F)
hq.heapify(B)

#Cを二分し、前半はFと、後半はBとで演算を行う
#演算方法(c in C)
#前半：cがF[0]より大きければF[0]を取り除くN個の一つとし、cをスコアに加える
#後半：-cがB[0]より大きければB[0]を取り除くN個の一つとし、cをスコアから引く
#どちらも場合も条件を満たさない場合はそのｃを取り除くN個の一つとする
#計算量：O(N*N*logN)
#途中計算をメモして計算量軽減
from copy import deepcopy
memoF = [0] * (N+1) #C[:i]を前半としたときのFとの演算結果の要素和
memoF[0] = sum(F)
memoB = [0] * (N+1) #C[i:]を後半としたときのBとの演算結果の要素和
memoB[N] = sum(B)
for i in range(N):
    if C[i] > F[0]:
        memoF[i+1] = memoF[i] + C[i] - hq.heapreplace(F, C[i])
    else:
        memoF[i+1] = memoF[i]

    if -C[N-1-i] > B[0]:
        memoB[N-1-i] = memoB[N-i] - C[N-1-i] - hq.heapreplace(B, -C[N-1-i])
    else:
        memoB[N-1-i] = memoB[N-i]

Scores = [memoF[i]+memoB[i] for i in range(N+1)]
ans = max(Scores)
print(ans)
# Original solution
import heapq

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

# 準備
left, right = A[:N], A[-N:]

right = list([-x for x in right])
left_sum, right_sum = [sum(left)], [-sum(right)]
heapq.heapify(left)
heapq.heapify(right)

# left処理
for i in range(N, 2*N):
    heapq.heappush(left, A[i])
    low = heapq.heappop(left)
    left_sum.append(left_sum[-1] + A[i] - low)

# right処理
for i in range(2*N-1, N-1, -1):
    heapq.heappush(right, -A[i])
    high = -heapq.heappop(right)
    right_sum.append(right_sum[-1] + A[i] - high)

# rightを逆順にしてleftの挙動と合わせる
right_sum = right_sum[::-1]

ans = max([l-r for l, r in zip(left_sum, right_sum)])
print(ans)


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

Left, Right = A[:N], list([-a for a in A[-N:]])
heapq.heapify(Left)
heapq.heapify(Right)
Left_SUM, Right_SUM = [sum(Left)], [-sum(Right)]

M = A[N:2*N]
# 左側
for k in range(N):
    lo = heapq.heappushpop(Left, M[k])
    Left_SUM.append(Left_SUM[-1] + M[k] - lo)

# 右側
for k in reversed(list(range(N))):
    hi = -heapq.heappushpop(Right, -M[k])
    Right_SUM.append(Right_SUM[-1] + M[k] - hi)

# 最大値を計算
ans = max([l - r for l, r in zip(Left_SUM, Right_SUM[::-1])])
print(ans)
# Original solution
import heapq
import copy

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

ante, post = alist[:n], alist[-n:]
startante = sum(ante)
startpost = sum(post)
post = list([-x for x in post])
heapq.heapify(ante)
heapq.heapify(post)

ans = None
for k in range(n+1):
  _ante = copy.deepcopy(ante)
  _post = copy.deepcopy(post)
  antesum = startante
  postsum = startpost
  for a in alist[n: n+k]:
    minante = heapq.heappushpop(_ante, a)
    antesum = antesum + a - minante
  for a in alist[n+k: 2*n]:
    maxpost = heapq.heappushpop(_post, -a)
    postsum = postsum + a + maxpost
  if ans is None:
    ans = antesum - postsum
  elif ans < antesum - postsum:
    ans = antesum - postsum
print(ans)


# Optimized solution
import heapq

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

ante, post = alist[:n], alist[-n:]
antesums = [0 for _ in range(n+1)]
postsums = [0 for _ in range(n+1)]
antesums[0] = sum(ante)
postsums[0] = sum(post)
post = list([-x for x in post])
heapq.heapify(ante)
heapq.heapify(post)

for k in range(n):
  minante = heapq.heappushpop(ante, alist[n+k])
  antesums[k+1] = antesums[k] + alist[n+k] - minante
  maxpost = heapq.heappushpop(post, -alist[2*n-k-1])
  postsums[k+1] = postsums[k] + alist[2*n-k-1] + maxpost

ans = -sum(alist)
for k in range(n+1):
  if ans < antesums[k] - postsums[-k-1]:
    ans = antesums[k] - postsums[-k-1]
print(ans)
# Original solution
N=int(eval(input()))
A=list(map(int,input().split()))
from collections import deque
import bisect
x,y,z=[],[],[]
for i in range(3*N):
    if 0<=i<N:x.append(A[i])
    elif N<=i<2*N:y.append(A[i])
    elif 2*N<=i<3*N:z.append(A[i])

a=x+y
a.sort()
mae=[sum(a[N:2*N])]
line=N-1
used=set()
for i in range(N-1,-1,-1):
    while line in used:
        line-=1
    idx=bisect.bisect_left(a,y[i])
    while idx in used:
        idx+=1
    used|={idx,}
    if line<idx:
        mae.append(mae[-1]-a[idx]+a[line])
        line-=1
    elif line==idx:
        mae.append(mae[-1])
        line-=1
    else:
        mae.append(mae[-1])

b=y+z
b.sort()
ushiro=[-1*sum(b[0:N])]
line=N
used=set()
for i in range(N):
    while line in used:
        line+=1
    idx=bisect.bisect_left(b,y[i])
    while idx in used:
        idx+=1
    used|={idx,}
    if idx<line:
        ushiro.append(ushiro[-1]+b[idx]-b[line])
        line+=1
    elif idx==line:
        ushiro.append(ushiro[-1])
        line+=1
    else:
        ushiro.append(ushiro[-1])
ans=-1*float('inf')
for i in range(N+1):
    ans=max(ans,mae[i]+ushiro[N-i])
print(ans)

# Optimized solution
from heapq import heappush,heappop
dataX=[]
dataY=[]
mae=dict()
ushiro=dict()
N=int(eval(input()))
A=list(map(int,input().split()))
X=A[0:N]
Y=A[N:2*N]
Z=A[2*N:3*N]
for i in range(N):
    heappush(dataX,X[i])
    heappush(dataY,-1*Z[i])
mae[0]=sum(X)
ushiro[0]=-1*sum(Z)
for i in range(1,N+1):
    mae[i]=mae[i-1]+Y[i-1]
    heappush(dataX,Y[i-1])
    mae[i]-=heappop(dataX)
    ushiro[i]=ushiro[i-1]-Y[N-i]
    heappush(dataY,-1*Y[N-i])
    ushiro[i]-=heappop(dataY)
ans=-1*float('inf')
for i in range(N+1):
    ans=max(ans,mae[i]+ushiro[N-i])
print(ans)
# Original solution
N = int(eval(input()))
import heapq as h
A = list(map(int, input().split()))


# use 0 based index
sum_red, sum_blue = [], []

head = A[:N]
tail = [-x for x in A[-N:]]
h.heapify(head)
h.heapify(tail)
sum_red.append(sum(head))
sum_blue.append(-sum(tail))
for k in range(N, 2*N):
    h.heappushpop(head, A[k])
    sum_red.append(sum(head))
    h.heappushpop(tail, -A[-k-1])
    sum_blue.append(-sum(tail))


print((max([r-b for r, b in zip(sum_red, sum_blue[::-1])])))


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


# use 0 based index
sum_red, sum_blue = [], []

head = A[:N]
tail = [-x for x in A[-N:]]
h.heapify(head)
h.heapify(tail)
sum_red.append(sum(head))
sum_blue.append(-sum(tail))
# keypoint: いちいちsumすると線形時間かかるのでsum_hoge[-1]でアクセスする
for k in range(N, 2*N):
    num_sub = h.heappushpop(head, A[k])
    sum_red.append(sum_red[-1]-num_sub+A[k])
    num_sub = -h.heappushpop(tail, -A[-k-1])
    sum_blue.append(sum_blue[-1]-num_sub+A[-k-1])


print((max([r-b for r, b in zip(sum_red, sum_blue[::-1])])))
# Original solution
import heapq
N = int( eval(input()))
A = list( map( int, input().split()))
fsum = [0]*(N+1)
bsum = [0]*(N+1)
forward = A[:N]
back = A[2*N:]
back = list([-x for x in back])
heapq.heapify(forward)
heapq.heapify(back)
fsum[0] = sum(forward)
bsum[N] = -sum(back)
for i in range(1,N+1):
    heapq.heappushpop(forward, A[N+i-1])
    fsum[i] = sum(forward)
    heapq.heappushpop(back, -A[2*N-i])
    bsum[N-i] = -sum(back)
ans = fsum[0] - bsum[0]
for i in range(1,N+1):
    ans = max(ans, fsum[i] - bsum[i])
print(ans)

# Optimized solution
import heapq
N = int( eval(input()))
A = list( map( int, input().split()))
fsum = [0]*(N+1)
bsum = [0]*(N+1)
forward = A[:N]
back = A[2*N:]
back = list([-x for x in back])
heapq.heapify(forward)
heapq.heapify(back)
fsum[0] = sum(forward)
fsumnow = fsum[0]
bsum[N] = -sum(back)
bsumnow = bsum[N]
for i in range(1,N+1):
    heapq.heappush(forward, A[N+i-1])
    fsumnow += A[N+i-1]
    fsumnow -= heapq.heappop(forward)
    fsum[i] = fsumnow
    heapq.heappush(back, -A[2*N-i])
    bsumnow += A[2*N-i]
    bsumnow += heapq.heappop(back)
    bsum[N-i] = bsumnow
ans = fsum[0] - bsum[0]
for i in range(1,N+1):
    ans = max(ans, fsum[i] - bsum[i])
print(ans)
# Original solution
N=int(eval(input()))
alist=list(map(int,input().split()))

#dp[3N][N]
dp=[[0 for _ in range(N+1)] for _ in range(3*N+1)]
for i in range(1,3*N+1):
  for j in range(1,N+1):
    if i<j:
      break
    dp[i][j]=max(dp[i-1][j],alist[i-1]+dp[i-1][j-1])
#print(dp)

alist_rev=alist[::-1]
dp_rev=[[float("inf") for _ in range(N+1)] for _ in range(3*N+1)]
dp_rev[0][0]=0
for i in range(1,3*N+1):
  dp_rev[i][0]=0
  for j in range(1,N+1):
    if i<j:
      break
    dp_rev[i][j]=min(dp_rev[i-1][j],alist_rev[i-1]+dp_rev[i-1][j-1])
#print(dp_rev)

slist=[]
for i in range(3*N+1):
  slist.append(dp[i][N])
  
slist_rev=[]
for i in range(3*N+1):
  slist_rev.append(dp_rev[-i-1][N])
  
#print(slist)
#print(slist_rev)

answer=-float("inf")
for i in range(N,2*N+1):
  score=slist[i]-slist_rev[i]
  answer=max(score,answer)
  
print(answer)

# Optimized solution
N=int(eval(input()))
alist=list(map(int,input().split()))

answer=-float("inf")
for i in range(N,2*N+1):
  alist1=alist[:i]
  alist2=alist[i:]
  #print(alist1,alist2)
  
  alist1.sort(reverse=True)
  alist2.sort()
  maxn_a1=sum(alist1[:N])
  minn_a2=sum(alist2[:N])
  #print(maxn_a1,minn_a2)
  answer=max(answer,maxn_a1-minn_a2)

print(answer)
# Original solution
import copy as cp
n = int(eval(input()))
a = input().split()
a = [int(m) for m in a]
t1 = []
t2 = []
t3 = []
for i in range(3 * n):
    if i < (3 * n) // 3:
        t1.append(a[i])
    elif (3 * n) // 3 <= i < (3 * n) // 3 * 2:
        t2.append(a[i])
    else:
        t3.append(a[i])
t1.sort()
t3.sort(reverse=True)
t2c = cp.deepcopy(t2)
t1c = cp.deepcopy(t1)
t3c = cp.deepcopy(t3)
y = []
for i in range(n + 1):
    if i == 0:
        u = sum(t1c)
        for j in range(n + 1):
            if j == 0:
                w = sum(t3c)
                x = u - w
                y.append(x)
            else:
                t3c.sort(reverse=True)
                t3c = t3c[1:] + t2c[-1:]
                t2c = t2c[:-1]
                w = sum(t3c)
                x = u - w
                y.append(x)
            t1c = t1
            t2c = t2
            t3c = t3
    else:
        t1c.sort()
        t1c = t1c[1:] + t2c[0:1]
        t2c = t2c[1:]
        u = sum(t1c)
        for j in range(n + 1 - i):
            if j == 0:
                w = sum(t3c)
                x = u - w
                y.append(x)
            else:
                t3c.sort(reverse=True)
                t3c = t3c[1:] + t2c[-1:]
                t2c = t2c[:-1]
                w = sum(t3c)
                x = u - w
                y.append(x)
        t2c = t2
        t3c = t3
        t1c = t1
print((max(y)))

# Optimized solution
from heapq import heappush, heappop
n = int(eval(input()))
a = input().split()
a = [int(m) for m in a]
t1 = []
t2 = []
mt3 = []
for i in range(3 * n):
    if i < (3 * n) // 3:
        t1.append(a[i])
    elif (3 * n) // 3 <= i < (3 * n) // 3 * 2:
        t2.append(a[i])
    else:
        mt3.append(-a[i])
t1.sort()
mt3.sort()
t1sumli = [sum(t1)]
t3sumli = [-sum(mt3)]
for i in range(n):
    pp = heappop(t1)
    heappush(t1, max(pp, t2[i]))
    t1sumli.append(t1sumli[-1] - pp + max(pp, t2[i]))

for i in range(n - 1, -1, -1):
    qq = -heappop(mt3)
    heappush(mt3, -min(qq, t2[i]))
    t3sumli.append(t3sumli[-1] - qq + min(qq, t2[i]))

sumli = []
for i in range(n + 1):
    sumli.append(t1sumli[i] - t3sumli[-i-1])
print((max(sumli)))
# Original solution
from heapq import heapify, heapreplace
n = int(eval(input()))
a = list(map(int, input().split()))
a1 = a[:n]
heapify(a1)
a2 = a[n:2*n]
a3 = [-i for i in a[2*n:]]
heapify(a3)
b1 = [sum(a1)]
b2 = [sum(a3)]
for i in range(n):
    b1.append(a2[i]-heapreplace(a1, a2[i]))
    b2.append(-heapreplace(a3, -a2[n-i-1])-a2[n-i-1])
for i in range(n):
    b1[i+1] += b1[i]
    b2[i+1] += b2[i]
accu = []
mx = b1[0]
for i in b1:
    mx = max(mx, i)
    accu.append(mx)
ans = -10**16
mx = b2[0]
for i in range(n+1):
    mx = max(mx, b2[i])
    ans = max(ans, mx+accu[n-i])
print(ans)

# Optimized solution
from heapq import heapify, heappushpop
n = int(eval(input()))
a = list(map(int, input().split()))
a1 = a[:n]
heapify(a1)
a2 = a[n:2*n]
a3 = [-i for i in a[2*n:]]
heapify(a3)
b1 = [sum(a1)]
b2 = [sum(a3)]
for i in range(n):
    b1.append(b1[-1]+a2[i]-heappushpop(a1, a2[i]))
    b2.append(b2[-1]-heappushpop(a3, -a2[n-i-1])-a2[n-i-1])
ans = b1[0]+b2[n]
for i in range(n+1):
    ans = max(ans, b1[i]+b2[n-i])
print(ans)
# Original solution
def f(a):
 q=a[:n];s=sum(q);heapify(q);yield s
 for e in a[n:2*n]:s+=e-heappushpop(q,e);yield s
from heapq import*;r=reversed;n,*a=list(map(int,open(0).read().split()));print((max(list(map(sum,list(zip(f(a),r(list(f([-e for e in r(a)]))))))))))

# Optimized solution
def f(a):
    q=a[:n];s=sum(q);heapify(q);yield s
    for e in a[n:2*n]:s+=e-heappushpop(q,e);yield s
from heapq import*;n,*a=list(map(int,open(0).read().split()));print((max(list(map(sum,list(zip(f(a),list(f([-e for e in a[::-1]]))[::-1])))))))
# Original solution
def f(x):
    y=x[:n];heapify(y);z=sum(y);s=[z]
    for i in x[n:n*2]:z+=i-heappushpop(y,i);s+=[z]
    return s
from heapq import*;n,*a=list(map(int,open(0).read().split()));print((max(list(map(sum,list(zip(f([-i for i in a[n:][::-1]]),f(a)[::-1])))))))

# Optimized solution
def f(x):
    y=x[:n];heapify(y);z=sum(y);yield z
    for i in x[n:n*2]:z+=i-heappushpop(y,i);yield z
from heapq import*;n,*a=list(map(int,open(0).read().split()));print((max(list(map(sum,list(zip(f([-i for i in a[n:][::-1]]),list(f(a))[::-1])))))))
# Original solution
import heapq 
N=int(eval(input()))
A=list(map(int, input().split()))
A_rev = [-x for x in A[::-1]]#逆順にして各要素を-1倍する
ans=-float("inf")
for k in range(N, 2*N+1):
	left=A[:k]
	right=A_rev[:(3*N-k)]

	heapq.heapify(left)
	heapq.heapify(right)

	for _ in range(k-N):
		heapq.heappop(left)
	for _ in range(2*N-k):
		heapq.heappop(right)

	ans= max(sum(left)+sum(right), ans)
print(ans)

# Optimized solution
#########################ABC解説実装#########################
import heapq
N=int(eval(input()))
A=list(map(int, input().split()))

left, right = A[:N], [-1 * i for i in A[2*N:]]
sum_left, sum_right = sum(left), sum(right)

results = [0] * (N+1)
results[0] = sum_left
results[N] = sum_right

heapq.heapify(left)
heapq.heapify(right)

for i in range(N, 2*N):
    v = A[i]
    p = heapq.heappushpop(left, v)
    sum_left += v - p
    results[i-N+1] += sum_left
    
for i in range(2*N-1, N-1, -1):
    v = -1 * A[i]
    p = heapq.heappushpop(right, v)
    sum_right += v - p
    results[i-N] += sum_right
print((max(results)))
# Original solution
import heapq

N = int(eval(input()))
a_list = list(map(int, input().split()))

max_score = - float("inf")

red_list = a_list[:N]
blue_list = [-a for a in a_list[2 * N:]]
heapq.heapify(red_list)
heapq.heapify(blue_list)
red_sum = [sum(red_list)]
blue_sum = [sum(blue_list)]

for i in range(N, 2 * N):
    heapq.heappush(red_list, a_list[i])
    item = heapq.heappop(red_list)
    red_sum.append(max(red_sum[-1], red_sum[-1] + a_list[i] - item))

for i in range(2 * N - 1, N - 1, -1):
    heapq.heappush(blue_list, -a_list[i])
    item = heapq.heappop(blue_list)
    blue_sum.append(max(blue_sum[-1], blue_sum[-1] - a_list[i] - item))

for i in range(N+1):
    score = red_sum[i] + blue_sum[-(i + 1)]
    if max_score < score:
        max_score = score
print(max_score)


# Optimized solution
import heapq

N = int(eval(input()))
a_list = list(map(int, input().split()))

max_score = - float("inf")

red_list = a_list[:N]
blue_list = [-a for a in a_list[2 * N:]]
heapq.heapify(red_list)
heapq.heapify(blue_list)
red_sum = [sum(red_list)]
blue_sum = [sum(blue_list)]

for i in range(N, 2 * N):
    heapq.heappush(red_list, a_list[i])
    item = heapq.heappop(red_list)
    red_sum.append(red_sum[-1] + a_list[i] - item)

for i in range(2 * N - 1, N - 1, -1):
    heapq.heappush(blue_list, -a_list[i])
    item = heapq.heappop(blue_list)
    blue_sum.append(blue_sum[-1] - a_list[i] - item)

for i in range(N+1):
    score = red_sum[i] + blue_sum[-(i + 1)]
    if max_score < score:
        max_score = score
print(max_score)
# Original solution
from heapq import heapify, heappop, heappush
from collections import deque

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

L = a[:n]
sum_l = [sum(L)]
heapify(L)

ML = a[n:2 * n]
ML = deque(ML)

R = list([(-1) * x for x in a[2 * n:]])
sum_r = [sum(R)]  # あとでReverseする
heapify(R)

MR = list([(-1) * x for x in a[n:2 * n]])
MR = deque(MR)

for i in range(n):
    add_to_l = ML.popleft()
    heappush(L, add_to_l)
    subtract_to_l = heappop(L)

    t = sum_l[-1] + add_to_l - subtract_to_l
    sum_l.append(t)

# print(sum_l)

for i in range(n):
    add_to_r = MR.pop()
    heappush(R, add_to_r)
    subtract_to_r = heappop(R)

    t = sum_r[-1] + add_to_r - subtract_to_r
    sum_r.append(t)

# print(sum_r)

sum_r = sum_r[::-1]

ans = sum_l[0] + sum_r[0]
for i in range(1, n + 1):
    t = sum_l[i] + sum_r[i]
    ans = max(ans, t)

print(ans)

# Optimized solution
def main():
    from heapq import heappush, heappushpop

    n = int(eval(input()))
    *a, = list(map(int, input().split()))  # [0,n),[n,2n),[2n,3n)

    to_rm = [0] * (n * 3)

    h = []
    for x in a[:n]:
        heappush(h, x)

    mid = tuple(enumerate(a[n:n * 2], n))

    t = 0
    for i, x in mid:
        mi = heappushpop(h, x)
        t += mi
        to_rm[i] = -t

    h = []
    for x in a[n * 2:n * 3]:
        heappush(h, -x)

    t = 0
    for i, x in reversed(mid):
        ma = -heappushpop(h, -x)
        t += ma
        to_rm[i - 1] += t

    tot = sum(a)
    ret = -10 ** 30
    s = sum(a[:n - 1])
    for tail in range(n - 1, n * 2):
        s += a[tail]
        ret = max(ret, s - (tot - s) + to_rm[tail])  # [0,tail]=前半
    print(ret)


if __name__ == '__main__':
    main()
# Original solution
# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/arc074/editorial.pdf
・優先度付きキュー
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from heapq import heappush, heappushpop

N = int(eval(input()))
aN = list(map(int, input().split()))

mids = aN[N:N*2]
L = []
R = []
for i in range(N):
    # とりあえず前後半確定の部分をキューに詰める
    heappush(L, aN[i])
    heappush(R, -aN[i+N*2])

# 未確定の真ん中1/3について調べていく
l_sum = [0] * (N+1)
l_sum[0] = sum(aN[:N])
for i in range(N):
    # ある値をpushして最小値をpopする
    num = heappushpop(L, mids[i])
    # それに合わせて合計値も更新
    l_sum[i+1] = l_sum[i] + mids[i] - num

# 後半部分は逆方向からやる
r_sum = [0] * (N+1)
r_sum[N] = sum(aN[N*2:])
for i in range(N-1, -1, -1):
    # 正負逆転させれば最大値にも使える
    num = -(heappushpop(R, -mids[i]))
    r_sum[i] = r_sum[i+1] + mids[i] - num

ans = -float('inf')
for i in range(N+1):
    ans = max(l_sum[i] - r_sum[i], ans)
print(ans)


# Optimized solution
# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/arc074/editorial.pdf
・優先度付きキュー
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from heapq import heapify, heappushpop

N = int(eval(input()))
aN = list(map(int, input().split()))

mids = aN[N:N*2]
# とりあえず前後半確定の部分をキューに詰める
L = aN[:N]
R = [-aN[i] for i in range(N*2, N*3)]
heapify(L)
heapify(R)

# 未確定の真ん中1/3について調べていく
l_sum = [0] * (N+1)
l_sum[0] = sum(aN[:N])
for i in range(N):
    # ある値をpushして最小値をpopする
    num = heappushpop(L, mids[i])
    # それに合わせて合計値も更新
    l_sum[i+1] = l_sum[i] + mids[i] - num

# 後半部分は逆方向からやる
r_sum = [0] * (N+1)
r_sum[N] = sum(aN[N*2:])
for i in range(N-1, -1, -1):
    # 正負逆転させれば最大値にも使える
    num = -(heappushpop(R, -mids[i]))
    r_sum[i] = r_sum[i+1] + mids[i] - num

ans = -float('inf')
for i in range(N+1):
    ans = max(l_sum[i] - r_sum[i], ans)
print(ans)
# Original solution
import heapq, copy
N = int(eval(input()))
A = [int(i) for i in input().split()]
Aleft = copy.deepcopy(A[:N])
sumLeft = sum(Aleft)
heapq.heapify(Aleft)
Aright = sorted(copy.deepcopy(A[N:]))
Rlim = Aright[N-1]
sumRight = sum(Aright[:N])
score = sumLeft - sumRight

for i in range(N):
    a = A[N+i]
    heapq.heappush(Aleft, a)
    sumLeft += a - heapq.heappop(Aleft)
    Aright.remove(a)
    if a <= Rlim:
        Rlim = Aright[N-1]
        sumRight += Rlim - a
    score = max(score, sumLeft - sumRight)
print(score)

# Optimized solution
import heapq
N = int(eval(input()))
A = [int(i) for i in input().split()]

sumLeft = [0] * (N+1) #A[:N+i]中のN要素の和の最大値のリスト
sumLeft[0] = sum(A[:N])
Aleft = A[:N]
heapq.heapify(Aleft)

sumRight = [0] * (N+1) #A[N+i:]中のN要素の和の最小値のリスト
sumRight[-1] = sum(A[2*N:]) 
Aright = [-1*i for i in A[2*N:]] #最大値をpopするために要素を-1倍しておく
heapq.heapify(Aright)

for i in range(1, N+1):
    a = A[N+i-1]
    b = -1 * A[2*N-i]
    sumLeft[i] = sumLeft[i-1] + a - heapq.heappushpop(Aleft, a)
    sumRight[-1-i] = sumRight[-i] + heapq.heappushpop(Aright, b) - b

score = sumLeft[0] - sumRight[0]
for i in range(1, N+1):
    score = max(score, sumLeft[i] - sumRight[i])
print(score)
# Original solution
import itertools
import copy
N=eval(input())
a=[]
a=list(map(int, input().split()))
#print N
#print a

n_l=[ i for i in range(len(a))]
#print n_l
c = list(itertools.combinations(n_l,N))
#c=[(3,1)]
#print c

score=0.1
for i in c:
	a_t=copy.deepcopy(a)
	#print "#Loop start"
	#print i
	for j in range(N):
		a_t.pop(i[j]-j)
	#print a_t
	a1=list(zip(*[iter(a_t)]*N))
	#print a1
	if score==0.1 or score<sum(a1[0])-sum(a1[1]):
		score=sum(a1[0])-sum(a1[1])
		#print "score::"+str(score)

print(score)

# Optimized solution
import itertools
from heapq import heapify,heappush,heappop

N=eval(input())
a=[]
a=list(map(int, input().split()))
a1=a[0:N]
#print a1

heapify(a1)

l1=[]
sum_a1=sum(a1)
l1.append(sum_a1)

# Max
for i in range(N,2*N):
	if a[i]>a1[0]:
		sum_a1=sum_a1+a[i]-a1[0]
		heappop(a1)
		heappush(a1, a[i])

	l1.append(sum_a1)


l2=[]
a2=[ -x for x in a[2*N:3*N]]
heapify(a2)
sum_a2=-1*sum(a2)
l2.append(sum_a2)

# Min
for i in reversed(list(range(N,2*N))):
	if a[i]<-1*a2[0]:
		sum_a2=sum_a2+a[i]-(-1*a2[0])
		heappop(a2)
		heappush(a2,-1*a[i])
	l2.append(sum_a2)


ans=[]
for i in range(N+1):
	ans.append(l1[i]-l2[N-i])

print(max(ans))
# Original solution
import itertools
import datetime
from heapq import heapify,heappush,heappop



N=eval(input())
a=[]
a=list(map(int, input().split()))
a1=a[:N]
#print a1


heapify(a1)

l1=[]
sum_a1=sum(a1)
l1.append(sum_a1)



# Max
for i in range(N,2*N):
	if a[i]>a1[0]:
		sum_a1=sum_a1+a[i]-a1[0]
		heappop(a1)
		heappush(a1, a[i])

	l1.append(sum_a1)

 

l2=[]
a2=[ -x for x in a[2*N:]]
heapify(a2)
sum_a2=-1*sum(a2)
l2.append(sum_a2)

# Min
for i in reversed(list(range(N,2*N))):
	if a[i]<-1*a2[0]:
		sum_a2=sum_a2+a[i]-(-1*a2[0])
		heappop(a2)
		heappush(a2,-1*a[i])
	l2.append(sum_a2)


ans=[]
for i in range(N+1):
	heappush(ans, -1*(l1[i]-l2[N-i]))

print(ans[0]*-1)



# Optimized solution
n=int(eval(input()))
import heapq
a=list(map(int, input().split()))
q=a[:n]
heapq.heapify(q)
x=[sum(q)]
for k in range(n,2*n):
    v=heapq.heappushpop(q,a[k])
    x.append(x[-1]+a[k]-v)
a=a[::-1]
q=[-v for v in a[:n]]
heapq.heapify(q)
y=[-sum(q)]
for k in range(n,2*n):
    v=-heapq.heappushpop(q,-a[k])
    y.append(y[-1]+a[k]-v)
print((max(v-w for v,w in zip(x,y[::-1]))))