Let N be a positive integer.
There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}).
Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements.
Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').
Find the maximum possible score of a'.

-----Constraints-----
 - 1 ≤ N ≤ 10^5
 - a_i is an integer.
 - 1 ≤ a_i ≤ 10^9

-----Partial Score-----
 - In the test set worth 300 points, N ≤ 1000.

-----Input-----
Input is given from Standard Input in the following format:
N
a_1 a_2 ... a_{3N}

-----Output-----
Print the maximum possible score of a'.

-----Sample Input-----
2
3 1 4 1 5 9

-----Sample Output-----
1

When a_2 and a_6 are removed, a' will be (3, 4, 1, 5), which has a score of (3 + 4) - (1 + 5) = 1.

Difficulty: interview

Starter code:

Solutions:
import heapq

data = int(input())
array = [int(_) for _ in input().split()]

X = array[0:data]
B = array[data:2*data]
Y = [-_ for _ in array[2*data:3*data]]

heapq.heapify(X)
heapq.heapify(Y)

x = [sum(X)]
y = [sum(Y)]

for i in range(data):
    x += [B[i] - heapq.heappushpop(X, B[i])]
    y += [-B[-1-i] - heapq.heappushpop(Y, -B[-1-i])]

for i in range(data):
    x[i+1] = x[i]+x[i+1]
    y[i+1] = y[i]+y[i+1]

print(max([x[_] + y[-1 - _] for _ in range(data+1)]))

from heapq import heappop, heappush, heapify


def main():
    n = int(input())
    A = list(map(int, input().split()))

    left_sums = []
    left = A[:n]
    left_sum = sum(left)
    left_sums.append(left_sum)
    heapify(left)

    for a in A[n:2*n]:
        left_sum += a
        heappush(left, a)
        left_sum -= heappop(left)
        left_sums.append(left_sum)

    right_sums = []
    right = []
    for a in A[2*n:]:
        right.append(-a)
    right_sum = sum(right)
    right_sums.append(-right_sum)
    heapify(right)

    for a in A[2*n-1:n-1:-1]:
        right_sum += -a
        heappush(right, -a)
        right_sum -= heappop(right)
        right_sums.append(-right_sum)

    candidates = []
    for sum1, sum2 in zip(left_sums, right_sums[::-1]):
        candidates.append(sum1 - sum2)

    print(max(candidates))


def __starting_point():
    main()
__starting_point()

import sys
readline = sys.stdin.readline

N = int(readline())
A = list(map(int,readline().split()))

# (1).左からN + 1～2N個のデータについて、iがいくつあるかのdictionary
# (2).左から2N個のデータのうち、大きい順にN個のデータの和
# (3).左から2N個のデータのうち、小さい順にN個のデータを、大きい順にheapqに入れたもの
# (4).右からN個のデータの和
# (5).右からN個のデータを、大きい順にheapqに入れたもの

# 上記を用いて、iを2N～N+1までずらし、そのたびに
# A[i]の数を(1)から減らす
# 次の数を(3)から取り出す。その数が(1)に存在していなければ何もしない
# 取り出した数を(2)に足す
# (4)にA[i]を足す
# (5)から一つ取り出し、(4)から引く
# (2) - (4)の最大値を更新

from collections import defaultdict

sortA = sorted(A[:2 * N])
smallA = sortA[:N]
small_dic = defaultdict(int)
for i in range(len(smallA)):
  small_dic[smallA[i]] += 1
largeA = sortA[N:]
large_dic = defaultdict(int)
for i in range(len(largeA)):
  large_dic[largeA[i]] += 1

leftsum = sum(sortA[N:])

import heapq as hq
leftq = list([-x for x in smallA])
hq.heapify(leftq)

rightq = A[2 * N:]
rightsum = sum(rightq)
rightq = list([-x for x in rightq])
hq.heapify(rightq)

ans = leftsum - rightsum

#print("leftsum",leftsum,"rightsum",rightsum,"ans",ans)
for i in range(2 * N - 1, N - 1, -1):
  #print("i",i,"A[i]",A[i])
  if large_dic[A[i]] > 0: # 除外対象である場合
    large_dic[A[i]] -= 1
    leftsum -= A[i]
    while True:
      move = -hq.heappop(leftq)
      if small_dic[move] > 0:
        small_dic[move] -= 1
        break
    leftsum += move
    large_dic[move] += 1
    #print("leftsumから",A[i],"を除外",leftsum)
  else:
    small_dic[A[i]] -= 1
    
  hq.heappush(rightq, -A[i])
  rem = -hq.heappop(rightq)
  rightsum += A[i]
  rightsum -= rem
  
  if ans < leftsum - rightsum:
    ans = leftsum - rightsum
  #print("leftsum",leftsum,"rightsum",rightsum,"ans",ans)
    
print(ans)


from heapq import heappush, heappop, heappushpop
N = int(input())
A = [int(a) for a in input().split()]

def calc(L):
    s = sum(L[:N])
    h = []
    X = [s]
    for i in range(N):
        heappush(h, L[i])
    for i in range(N, 2*N):
        s += L[i] - heappushpop(h, L[i])
        X.append(s)
    return X

B = calc(A)
C = calc([-a for a in A][::-1])[::-1]
print(max([B[i] + C[i] for i in range(N+1)]))

import heapq

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

leftQue = []
rightQue = []

leftSum = 0
rightSum = 0

for i in range(N):
    heapq.heappush(leftQue, A[i])
    leftSum += A[i]

    heapq.heappush(rightQue, -A[-1 - i])
    rightSum -= A[-1 - i]

left = [-float('inf') for _ in range(3 * N)]
right = [-float('inf') for _ in range(3 * N)]

left[N - 1] = leftSum

for middle in range(N, 2 * N):
    leftSum += A[middle]
    leftSum -= heapq.heappushpop(leftQue, A[middle])
    left[middle] = leftSum

right[2 * N - 1] = rightSum
for middle in range(2 * N - 1, N - 1, -1):
    rightSum -= A[middle]
    rightSum -= heapq.heappushpop(rightQue, -A[middle])
    right[middle - 1] = rightSum

ans = -float('inf')
for l, r in zip(left, right):
    ans = max(ans, l + r)

print(ans)

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

b = list(enumerate(a))

l = sorted(b[:2*n], key=lambda x: x[1], reverse=True)
r = sorted(b[n:], key=lambda x: x[1])

big = [0] * (3*n)
small = [0] * (3*n)

for i, (pos, z) in enumerate(l):
    big[pos] = i
for i, (pos, z) in enumerate(r):
    small[pos] = i

first = sum(a[:n])
second = 0
for pos, z in r[:n]:
    second += z
i = 2 * n
j = n-1
ans = first - second
for split in range(n, 2*n):
    if big[split] < i:
        first += a[split]
        i -= 1
        while l[i][0] > split:
            i -= 1
        first -= l[i][1]
    if small[split] <= j:
        second -= a[split]
        j += 1
        while r[j][0] < split:
            j += 1
        second += r[j][1]
    ans = max(ans, first - second)
print(ans)

INF = 10 ** 20
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from  heapq import heappop,heapify,heappush

def main():
    n = int(input())
    a = list(map(int,input().split()))
    
    lM = [0] * (n + 1)
    rm = [0] * (n + 1)

    q = []
    cumsum = 0
    for i in range(n):
        heappush(q,a[i])
        cumsum += a[i]
    
    lM[0] = cumsum
    drop = 0
    for i in range(n,2 * n):
        heappush(q,a[i])
        drop += heappop(q)
        cumsum += a[i]
        lM[i - n + 1] = cumsum - drop
    
    q = []
    cumsum = 0
    for i in range(3 * n - 1,2 * n - 1,-1):
        heappush(q,-a[i])
        cumsum += a[i]
    
    rm[-1] = cumsum
    drop = 0
    for i in range(2 * n - 1,n - 1,-1):
        heappush(q,-a[i])
        drop -= heappop(q)
        cumsum += a[i]
        rm[i - n] = cumsum - drop
    
    ans = -INF
    for i in range(n + 1):
        ans = max(ans,lM[i] - rm[i])
        
    print(ans)
def __starting_point():
    main()

__starting_point()

import sys
import heapq

def main():
    rl=sys.stdin.readline
    n=int(rl().strip())
    a=list(map(int,rl().strip().split()))
    b=[-x for x in a]
    b.reverse()
    fl=a[:n]
    fs=sum(fl)
    ll=b[:n]
    ls=sum(ll)
    fdl=[0]*(n+1)
    ldl=[0]*(n+1)
    heapq.heapify(fl)
    heapq.heapify(ll)
    for i in range(1,n+1):
        fmn=heapq.heappushpop(fl,a[n+i-1])
        lmn=heapq.heappushpop(ll,b[n+i-1])
        fdl[i]=fdl[i-1]+a[n+i-1]-fmn
        ldl[i]=ldl[i-1]+b[n+i-1]-lmn
    ldl.reverse()
    dif=max([x+y for x,y in zip(fdl,ldl)])
    print((fs+ls+dif))

def __starting_point():
    main()


__starting_point()

import heapq

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

sa = 0
sb = 0
hf = []
hb = []
la = [[0]*2 for i in range(n+1)]
for i in range(n):
    sa += A[i]
    heapq.heappush(hf,A[i])
for i in range(2*n,3*n):
    sb += A[i]
    heapq.heappush(hb,-A[i])
la[0][0] = sa
la[-1][-1] = sb
for i in range(n,2*n):
    now = A[i]
    now2 = A[-1-i]
    heapq.heappush(hf,now)
    heapq.heappush(hb,-now2)
    h1 = heapq.heappop(hf)
    h2 = -heapq.heappop(hb)
    sa += now-h1
    sb += now2 -h2
    la[i-n+1][0] = sa
    la[-i+n-2][1] = sb

ans = -float("INF")
for i,j in la:
    ans = max(ans,i-j)
print(ans)


import heapq

N = int(input())
A = [int(a) for a in input().split()]

L = A[:2*N]
L.sort()
s1 = 0
s2 = 0
h1 = []
h2 = []
dic = {}
dic_h = {}
for i in range(N):
    heapq.heappush(h1, -L[i])
    if L[i] in dic_h:
        dic_h[L[i]] += 1
    else:
        dic_h[L[i]] = 1
    s1 += L[i+N]
    if L[i+N] in dic:
        dic[L[i+N]] += 1
    else:
        dic[L[i+N]] = 1
    s2 += A[i+2*N]
    heapq.heappush(h2, -A[i+2*N])
    
ans = s1-s2
for i in range(2*N-1, N-1, -1):
    if A[i]+h2[0] < 0:
        s2 += heapq.heappop(h2)
        heapq.heappush(h2, -A[i])
        s2 += A[i]
    if A[i] in dic:
        if dic[A[i]] > 0:
            dic[A[i]] -= 1
            s1 -= A[i]
            t = -heapq.heappop(h1)
            while h1:
                if dic_h[t] > 0:
                    dic_h[t] -= 1
                    break
                else:
                    t = -heapq.heappop(h1)
            s1 += t
            if t in dic:
                dic[t] += 1
            else:
                dic[t] = 1
    else:
        dic_h[A[i]] -= 1
    ans = max(ans, s1-s2)
    
print(ans)

import heapq
n=int(input())
A=list(map(int,input().split()))
A_l=A[:n]
heapq.heapify(A_l)
A_l_sum=[sum(A_l)]
A_m=A[n:2*n]
for i in range(n):
    p=A_m[i]
    heapq.heappush(A_l,p)
    q=heapq.heappop(A_l)
    A_l_sum.append(A_l_sum[-1]+p-q)
A_r=A[2*n:3*n]
for i in range(n):
    A_r[i]*=-1
for i in range(n):
    A_m[i]*=-1
A_m=A_m[::-1]
heapq.heapify(A_r)
A_r_sum=[sum(A_r)]
for i in range(n):
    p=A_m[i]
    heapq.heappush(A_r,p)
    q=heapq.heappop(A_r)
    A_r_sum.append(A_r_sum[-1]+p-q)
ans=-float("INF")
for i in range(n+1):
    ans=max(ans,A_l_sum[i]+A_r_sum[-i-1])
print(ans)

import heapq
n= int(input())
a=list(map(int,input().split()))
pres = a[:n]
heapq.heapify(pres)
apresum = [0]*(n+1)
aps = sum(pres)
apresum[0]=aps
posts = list([-1 * x for x in a[::-1][:n]])
heapq.heapify(posts)
apossum = [0]*(n+1)
aqs = sum(posts)
apossum[0]=aqs
for i in range(1,n+1):
    tempprea = a[n+i-1]
    tempposta = -1 * a[2*n-i]
    heapq.heappush(pres,tempprea)
    tempprepop=heapq.heappop(pres)
    aps += tempprea-tempprepop
    apresum[i]=aps
    heapq.heappush(posts,tempposta)
    temppostpop=heapq.heappop(posts)
    aqs += tempposta - temppostpop
    apossum[i]=aqs
print((max([x+y for x,y in zip(apresum,apossum[::-1])])))


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

l_sum = [0 for _ in range(n+1)]
r_sum = [0 for _ in range(n+1)]

que = a[:n]
l_sum[0] = sum(que)
heapq.heapify(que)

for i in range(n):
    l_sum[i+1] = l_sum[i]

    if que[0] < a[n+i]:
        l_sum[i+1] += a[n+i] - que[0]
        heapq.heappop(que)
        heapq.heappush(que, a[n+i])


que = [-a[i] for i in range(2*n, 3*n)]
r_sum[0] = -sum(que)
heapq.heapify(que)

for i in range(n):
    r_sum[i+1] = r_sum[i]
    
    if -que[0] > a[2*n-1-i]:
        r_sum[i+1] += a[2*n-1-i] + que[0]
        heapq.heappop(que)
        heapq.heappush(que, -a[2*n-1-i])


ans = -1e15
for x in range(n+1):
    ans = max(ans, l_sum[x] - r_sum[n-x])

print(ans)

class HeapQueue:
    """
    q = HeapQueue()
    q.append(p, v)
    v = q.pop()
    """
    from heapq import heappop, heappush, heappushpop, heapreplace

    def __init__(self, reverse=False):
        self.reverse = reverse
        self.heap = []

    def __len__(self):
        return len(self.heap)

    def append(self, p, v):
        self.heappush(self.heap, (-p if self.reverse else p, v))

    def appendpop(self, p, v):
        return self.heappushpop(self.heap, (-p if self.reverse else p, v))[1]

    def popappend(self, p, v):
        return self.heapreplace(self.heap, (-p if self.reverse else p, v))[1]

    def pop(self):
        return self.heappop(self.heap)[1]

    def front(self):
        return self.heap[0][1]


N = int(input())
A = [int(s) for s in input().split()]
S = []
T = []

S.append(sum(A[:N]))
q = HeapQueue()
for a in A[:N]:
    q.append(a, a)
for a in A[N:2*N]:
    m = q.appendpop(a, a)
    S.append(S[-1] + a - m)

T.append(sum(A[-N:]))
q = HeapQueue(reverse=True)
for a in A[-N:]:
    q.append(a, a)
for a in A[-N-1:N-1:-1]:
    m = q.appendpop(a, a)
    T.append(T[-1] + a - m)
ans = max([S[i] - T[N - i] for i in range(N + 1)])
print(ans)


import heapq

n = int(input())
a = list(map(int, input().split()))
score = [[0, 0] for _ in range(n + 1)]
h1 = a[0 : n]
h2 = [-a[2 * n + i] for i in range(n)]
maxscore = sum(h1)
minscore = -sum(h2)
heapq.heapify(h1)
heapq.heapify(h2)
score[0][0] = maxscore
score[n][1] = minscore
for i in range(n):
    heapq.heappush(h1, a[n + i])
    heapq.heappush(h2, -a[2 * n - 1 - i])
    maxscore = maxscore + a[n + i] - heapq.heappop(h1)
    minscore = minscore + a[2 * n - 1 - i] + heapq.heappop(h2)
    score[i + 1][0] = maxscore
    score[n - 1 - i][1] = minscore
ans = -pow(10, 15)
for i in range(n + 1):
    ans = max(ans, score[i][0] - score[i][1])
print(ans)

from heapq import *
N = int(input())
A = list(map(int,input().split()))
L,C,R = A[:N],A[N:2*N],A[2*N:]
F = [sum(L)]
heapify(L)

for c in C:
  F.append(F[-1]+c-heappushpop(L,c))

R = [-r for r in R]
B = [sum(R)]
heapify(R)

for c in reversed(C):
  B.append(B[-1]-c-heappushpop(R,-c))

print(max(f+b for f,b in zip(F,reversed(B))))

from heapq import heappush, heappop

N = int(input())
a = [int(x) for x in input().split()]

left = sorted(a[:N])
max_left = [sum(left)]

right = sorted([-x for x in a[-N:]])
min_right = [sum(right) * -1]

for i in range(N, 2 * N):
    j = 3 * N - i - 1

    heappush(left, a[i])
    v = heappop(left)
    max_left.append(max_left[-1] - v + a[i])

    heappush(right, a[j] * -1)
    v = heappop(right) * -1
    min_right.append(min_right[-1] - v + a[j])

ans = float('-inf')
for l, r in zip(max_left, min_right[::-1]):
    ans = max(l - r, ans)
print(ans)


from heapq import heappop, heappush

inf = float('inf')

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

# sum_max[k] : [0,k)のうちN個までの総和の最大値
# sum_min[k] : (3N-1-k,3N-1]のうちN個までの総和の最小値
sum_max = [0]*(3*N+1)
sum_min = [0]*(3*N+1)

def init_max():
    res = 0
    hq = []
    for i, a in enumerate(A):
        if len(hq) < N:
            heappush(hq,a)
            res += a
        else:
            if hq[0] < a:
                res -= heappop(hq)
                heappush(hq,a)
                res += a
        sum_max[i+1] = res

def init_min():
    res = 0
    hq = []
    for i, a in enumerate(A[::-1]):
        if len(hq) < N:
            heappush(hq,-a)
            res += a
        else:
            if -hq[0] > a:
                res -= -heappop(hq) 
                heappush(hq,-a)
                res += a
        sum_min[i+1] = res

init_max()
init_min()

ans = -inf

for k in range(N,2*N+1):
    res = sum_max[k] - sum_min[3*N-k]
    ans = max(ans, res)

print(ans)

from heapq import heappop, heappush
inf = float('inf')

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

l = []
res = 0
for i in range(N):
    heappush(l, A[i])
    res += A[i]
ls = []
ls.append(res)

for i in range(N, 2*N):
    heappush(l, A[i])
    res += A[i]
    res -= heappop(l)
    ls.append(res)

A.reverse()

s = []
res = 0
for i in range(N):
    heappush(s, -A[i])
    res += A[i]
ss = []
ss.append(res)

for i in range(N, 2*N):
    heappush(s, -A[i])
    res += A[i]
    res -= -heappop(s)
    ss.append(res)

ss.reverse()

ans = -inf

for i in range(N+1):
    score = ls[i] - ss[i]
    ans = max(ans, score)

print(ans)

n=int(input())
a=list(map(int,input().split()))
ans=-10**18
a_minus=[-x for x in a]
af=a[:n]
ae=a_minus[2*n:]
f_sum=[sum(af)]
e_sum=[sum(ae)]
from heapq import heapify,heappop,heappush
heapify(af)
for aa in a[n:2*n]:
  heappush(af,aa)
  t=heappop(af)
  f_sum.append(f_sum[-1]+aa-t)
heapify(ae)
for aa in reversed(a[n:2*n]):
  heappush(ae,-aa)
  t=heappop(ae)
  e_sum.append(e_sum[-1]-aa-t)
for f,e in zip(f_sum,reversed(e_sum)):
  ans=max(ans,f+e)
print(ans)


import heapq

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

Q0 = []
Q1 = []
Ana = [0] * (3*n)

M = [[A[n+i], n+i] for i in range(2*n)]
M.sort() 

msum = sum([M[i][0] for i in range(n)])
ans = sum(A[:n]) - msum
ans0 = ans
#print(ans0)

for i in range(n):
    heapq.heappush(Q0, A[i])
    heapq.heappush(Q1, [M[n+i][0], M[n+i][1]])
    Ana[M[n+i][1]] = 1

for i in range(n):
    #print("i",i, Q0,Q1,Ana)
    if Ana[n+i] == 0:
        heapq.heappush(Q0, A[n+i])
        ans0 += A[n+i] * 2
        ochi = heapq.heappop(Q0)
        ans0 -= ochi
        agari = heapq.heappop(Q1)
        while Ana[agari[1]] == 0:
            agari = heapq.heappop(Q1)
        Ana[agari[1]] = 0
        ans0 -= agari[0]
    else:
        Ana[n+i] = 0
        heapq.heappush(Q0, A[n+i])
        ans0 += A[n+i]
        ochi = heapq.heappop(Q0)
        ans0 -= ochi
    #print(ans0)
    ans = max(ans, ans0)


saigo = sum((sorted(A[:n*2]))[n:]) - sum(A[n*2:])
#print(saigo)

ans = max(ans, saigo)

print(ans)

import heapq
n=int(input())
a=list(map(int,input().split()))
s1=sum(a[:n])
hq1=a[:n]
heapq.heapify(hq1)
A=[s1]
for i in range(n,2*n):
  s1+=a[i]
  heapq.heappush(hq1,a[i])
  x=heapq.heappop(hq1)
  s1-=x
  A.append(s1)
a=a[::-1]
s2=sum(a[:n])
hq2=[-a[i] for i in range(n)]
heapq.heapify(hq2)
B=[s2]
for i in range(n,2*n):
  s2+=a[i]
  heapq.heappush(hq2,-a[i])
  x=heapq.heappop(hq2)
  s2-=-x
  B.append(s2)
B=B[::-1]
ans=-10**18
for i in range(len(A)):
  ans=max(ans,A[i]-B[i])
print(ans)

N = int(input())
A = list(map(int,input().split()))
S = []
P = A[:N]
Q = A[2*N:]
for i in range(N):
    Q[i] *= -1
R = A[N:2*N]
p = [0]*(N+1)
q = [0]*(N+1)
import heapq
heapq.heapify(P)
heapq.heapify(Q)
sp = sum(P)
sq = sum(Q)
p[0] = sp
q[0] = sq

for i in range(1,N+1):
    heapq.heappush(P,R[i-1])
    x = heapq.heappop(P)
    heapq.heappush(Q,-R[-i])
    y = heapq.heappop(Q)
    sp = sp + R[i-1] - x
    sq = sq - R[-i] - y
    p[i] = sp
    q[i] = sq
ans = -(10**100)
for k in range(N+1):
    ans = max(ans,p[k] + q[N-k])
    
print(ans)

from heapq import heapify,heappop,heappush
N=int(input())
a=list(map(int,input().split()))
ans=-10**18
a_neg=[-x for x in a]
af=a[:N]
ae=a_neg[2*N:]
f_sum=[sum(af)]
e_sum=[sum(ae)]

heapify(af)
for aa in a[N:2*N]:
  heappush(af,aa)
  t=heappop(af)
  f_sum.append(f_sum[-1]+aa-t)

heapify(ae)
for aa in reversed(a[N:2*N]):
  heappush(ae,-aa)
  t=heappop(ae)
  e_sum.append(e_sum[-1]-aa-t)

for f,e in zip(f_sum,reversed(e_sum)):
  ans=max(ans,f+e)

print(ans)

import sys
from heapq import heapify,heappushpop

def main():
    rl=sys.stdin.readline
    n=int(rl().strip())
    a=list(map(int,rl().strip().split()))
    b=[-x for x in a]
    b.reverse()
    fl=a[:n]
    fs=sum(fl)
    ll=b[:n]
    ls=sum(ll)
    fdl=[0]*(n+1)
    ldl=[0]*(n+1)
    heapify(fl)
    heapify(ll)
    for i in range(1,n+1):
        fmn=heappushpop(fl,a[n+i-1])
        lmn=heappushpop(ll,b[n+i-1])
        fdl[i]=fdl[i-1]+a[n+i-1]-fmn
        ldl[i]=ldl[i-1]+b[n+i-1]-lmn
    ldl.reverse()
    dif=max([x+y for x,y in zip(fdl,ldl)])
    print((fs+ls+dif))

def __starting_point():
    main()


__starting_point()

from heapq import heapify, heappushpop

def abc062_d():
    n = int(input())
    A = list(map(int, input().split()))

    front = A[:n]
    fsum = [0] * (3*n)
    fsum[n-1] = sum(front)
    heapify(front)
    for i in range(n, 2*n):
        fmin = heappushpop(front, A[i])
        fsum[i] = fsum[i-1] + A[i] - fmin

    back = [-1*a for a in A[2*n:]]
    bsum = [0] * (3*n)
    bsum[2*n] = -1 * sum(back)
    heapify(back)
    for i in range(2*n-1, n-1, -1):
        bmax = -1 * heappushpop(back, -1*A[i])
        bsum[i] = bsum[i+1] + A[i] - bmax

    ans = -10**18
    for i in range(n-1, 2*n):
        ans = max(ans, fsum[i] - bsum[i+1])
    print(ans)

def __starting_point():
    abc062_d()
__starting_point()

import heapq

n = int(input())
A = list(map(int, input().split()))
Left_top = A[:n]
Right_bottom = [-i for i in A[-n:]]
L = [0]*(n+1)
R = [0]*(n+1)
L[0] = sum(Left_top)
R[-1] = sum(Right_bottom)
heapq.heapify(Left_top)
heapq.heapify(Right_bottom)
for i in range(n, 2*n):
  L[i-n+1] = L[i-n] - heapq.heappushpop(Left_top, A[i]) + A[i]
  R[2*n-i-1] = R[2*n-i] - heapq.heappushpop(Right_bottom, -A[-(i+1)]) - A[-(i+1)]
ans = -float("inf")
for i in range(n+1):
  ans = max(ans, L[i] + R[i])
print(ans)

import heapq as hp
import sys
input = sys.stdin.readline

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

q1 = []
for i in range(N):
    hp.heappush(q1, A[i])

Psum = [0]*(N+1)
Psum[0] = sum(q1)

for i in range(N):
    a1 = hp.heappop(q1)
    p = max(a1, A[N+i])
    hp.heappush(q1, p)
    Psum[i+1] = Psum[i] + p - a1

q2 = []
for i in range(N):
    hp.heappush(q2, -A[i+2*N])

Qsum = [0]*(N+1)
Qsum[N] = sum(q2)

for i in range(N-1, -1, -1):
    a2 = hp.heappop(q2)
    p = max(a2, -A[N+i])
    hp.heappush(q2, p)
    Qsum[i] = Qsum[i+1] + p - a2


for i in range(N+1):
    if i == 0:
        ans = Psum[i]+Qsum[i]
    ans = max(Psum[i]+Qsum[i], ans)
print(ans)

import heapq
def solve():
  n = int(input())
  a = list(int(i) for i in input().split())
  an = []
  a2n = a[n:2*n]
  a3n = []
  for i in range(n):
    heapq.heappush(an,a[i])
    heapq.heappush(a3n,-1*a[i+2*n])
  ta2n = a2n
  
  tmpsuman = sum(an)
  tmpsuma3n = -1*sum(a3n)
  
  suman = [tmpsuman]
  suma3n = [tmpsuma3n]
  
  for i in range(n):
    tmp = ta2n[i]
    tmpsuman += tmp
    heapq.heappush(an,tmp)
    tmpsuman -= heapq.heappop(an)
    
    suman.append(tmpsuman)
  for i in range(n):
    tmp = ta2n[n-i-1]
    tmpsuma3n += tmp
    heapq.heappush(a3n,-1*tmp)
    tmpsuma3n -= -1*heapq.heappop(a3n)
    suma3n.append(tmpsuma3n)

  ans = -10000000000000000
  for i in range(n+1):
    tmpans = suman[i]-suma3n[n-i]
    ans = max(ans,tmpans)
  print(ans)
solve()

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

    from heapq import heapify, heappushpop

    # first half
    fh = []
    l = a[:n]
    fh.append(sum(l))
    heapify(l)
    for i in a[n:2*n]:
        if l[0] < i:
            fh.append(fh[-1] + i - heappushpop(l, i))
        else:
            fh.append(fh[-1])

    # latter half
    lh = []
    l = [-i for i in a[2*n:]]
    lh.append(sum(l))
    heapify(l)
    for i in a[2*n-1:n-1:-1]:
        if l[0] < -i:
            lh.append(lh[-1] - i - heappushpop(l, -i))
        else:
            lh.append(lh[-1])

    ans = fh[0] + lh[n]
    for i in range(1, n+1):
        if ans < fh[i] + lh[n-i]:
            ans = fh[i] + lh[n-i]

    print(ans)

main()

import heapq
def main():
    N = int(input())
    A = list(map(int, input().split()))
    fl = [i for i in A[:N]]
    f = [sum(A[:N])]
    heapq.heapify(fl)
    ll = [-i for i in A[2*N:]]
    l = [sum(A[2*N:])]
    heapq.heapify(ll)
    for i in range(N):
        s = f[-1]
        if A[N+i] > fl[0]:
            s = s - fl[0] + A[N+i]
            heapq.heappushpop(fl, A[N+i])
        f.append(s)
        s = l[-1]
        if - A[2*N-1-i] > ll[0]:
            s = s + ll[0] + A[2*N-1-i]
            heapq.heappushpop(ll, -A[2*N-1-i])
        l.append(s)
    r = f[0] - l[-1]
    for i in range(N+1):
        r = max(r, f[i] - l[-1-i])
    return r
print((main()))


from collections import deque
from heapq import heapify, heappop, heappush
N = int(input())
tmp = list(map(int, input().split(' ')))
former_A = deque(tmp)
latter_A = deque(tmp.copy())
former_heap = list()
latter_heap = list()
for _ in range(N):
    former_heap.append(former_A.popleft())
    latter_heap.append(- latter_A.pop())
heapify(former_heap)
heapify(latter_heap)

former_sum = sum(former_heap)
former_sum_list = [former_sum]
for k in range(N):
    new_a = former_A.popleft()
    heappush(former_heap, new_a)
    min_a = heappop(former_heap)
    former_sum += new_a - min_a
    former_sum_list.append(former_sum)

latter_sum = sum(latter_heap)
latter_sum_list = [latter_sum]
for k in range(N):
    new_a = - latter_A.pop()
    heappush(latter_heap, new_a)
    min_a = heappop(latter_heap)
    latter_sum += new_a - min_a
    latter_sum_list.append(latter_sum)
latter_sum_list.reverse()

answer = max([former + latter for former, latter in zip(former_sum_list, latter_sum_list)])
print(answer)

from heapq import heapify, heappushpop

N, *A = map(int, open(0).read().split())

L, C, R = A[:N], A[N:2 * N], A[2 * N:]

F = [sum(L)]
heapify(L)
for c in C:
    F.append(F[-1] + c - heappushpop(L, c))

R = [-r for r in R]
B = [sum(R)]
heapify(R)
for c in reversed(C):
    B.append(B[-1] - c - heappushpop(R, -c))

print(max(f + b for f, b in zip(F, reversed(B))))

import heapq

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

L = A[:N]
heapq.heapify(L)
Lmax = [0] * (N + 1)
Lsum = sum(L)
Lmax[0] = Lsum
for i in range(N, 2 * N):
    m = heapq.heappushpop(L, A[i])
    Lsum += A[i] - m
    Lmax[i - N + 1] = Lsum

R = [-x for x in A[2 * N:]]
heapq.heapify(R)
Rmin = [0] * (N + 1)
Rsum = -sum(R)
Rmin[N] = Rsum
for i in range(2 * N - 1, N - 1, -1):
    M = -heapq.heappushpop(R, -A[i])
    Rsum -= M - A[i]
    Rmin[i - N] = Rsum

print((max(Lmax[i] - Rmin[i] for i in range(N + 1))))


from heapq import heapify, heappushpop
n = int(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)

import heapq

n = int(input())
a = list(map(int, input().split()))
plus = [sum(a[:n])]
minus = [-sum(a[-n:])]
p = a[:n]
m = [-i for i in a[-n:]]
heapq.heapify(p)
heapq.heapify(m)
for i in range(n,2*n):
  pn = a[i]
  mn = -a[-(i+1)]
  if pn > p[0]:
    plus.append(plus[-1] + pn - heapq.heappop(p))
    heapq.heappush(p, pn)
  else:
    plus.append(plus[-1])
  if mn > m[0]:
    minus.append(minus[-1] + mn - heapq.heappop(m))
    heapq.heappush(m, mn)
  else:
    minus.append(minus[-1])
minus.reverse()
ans = []
for i,j in zip(plus,minus):
  ans.append(i+j)
print(max(ans))

from heapq import heappop,heappush,heapify
n=int(input())
a=list(map(int,input().split()))
left=[0]*n
lst=a[:n]
s=sum(lst)
heapify(lst)
for i in range(n):
    heappush(lst,a[n+i])
    x=heappop(lst)
    if i==0:
        left[0]=s+a[n]-x
    else:
        left[i]=left[i-1]+a[n+i]-x
left=[s]+left
right=[0]*n
lst=[]
for i in range(2*n,3*n):
    lst.append(-a[i])
s=-sum(lst)
heapify(lst)
for i in range(n):
    heappush(lst,-a[2*n-1-i])
    x=-heappop(lst)
    if i==0:
        right[n-1]=s+a[2*n-1]-x
    else:
        right[n-1-i]=right[n-i]+a[2*n-1-i]-x
right+=[s]
ans=-float("inf")
for i in range(n+1):
    ans=max(ans,left[i]-right[i])
print(ans)

import heapq

n=int(input())
arr=list(map(int,input().split()))
q1=[]
tmp=0
for val in arr[:n]:
  heapq.heappush(q1,val)
  tmp+=val
sum1=[tmp]
for val in arr[n:2*n]:
  tmp=heapq.heappop(q1)
  if val>tmp:
    heapq.heappush(q1,val)
    sum1.append(sum1[-1]+(val-tmp))
  else:
    heapq.heappush(q1,tmp)
    sum1.append(sum1[-1])
q2=[]
tmp=0
for val in arr[2*n:]:
  heapq.heappush(q2,-val)
  tmp+=val
sum2=[tmp]
for val in arr[2*n-1:n-1:-1]:
  tmp=-heapq.heappop(q2)
  if val<tmp:
    heapq.heappush(q2,-val)
    sum2.append(sum2[-1]+(val-tmp))
  else:
    heapq.heappush(q2,-tmp)
    sum2.append(sum2[-1])
sum2=sum2[::-1]
ans=-10**18
for i in range(n+1):
  tmp=sum1[i]-sum2[i]
  ans=max(ans,tmp)
print(ans)

import heapq
N=int(input())
a=list(map(int,input().split()))
l=[None]*(N+1)
r=[None]*(N+1)
h=a[:N]
s=sum(h)
heapq.heapify(h)
l[0]=s
for i in range(N):
    heapq.heappush(h,a[i+N])
    s+=a[i+N]-heapq.heappop(h)
    l[i+1]=s
h=list(map(lambda x:-x,a[2*N:]))
heapq.heapify(h)
s=sum(h)
r[-1]=s
for i in range(N):
    heapq.heappush(h,-a[-N-i-1])
    s+=-a[-N-i-1]-heapq.heappop(h)
    r[-i-2]=s
a=l[0]+r[0]
for i in range(1,N+1):
    if a<l[i]+r[i]:
        a=l[i]+r[i]
print(a)

from heapq import heappush, heappop
N = int(input())
A = [int(a) for a in input().split()]
dpx = [0]*(N+1)
dpy = [0]*(N+1)
dpx[0] = sum(A[:N])
dpy[-1] = sum(A[2*N:])
X = []
Y = []
for i in range(N):
  heappush(X,A[i])

for i in range(N):
  heappush(Y,-A[3*N-1-i])

for i in range(N):
  a = heappop(X)
  b = A[N+i]
  if b>a:
    heappush(X,b)
    dpx[i+1] = dpx[i]+b-a
  else:
    heappush(X,a)
    dpx[i+1] = dpx[i]
  
  c = -heappop(Y)
  d = A[2*N-1-i]
  if d<c:
    heappush(Y,-d)
    dpy[N-1-i] = dpy[N-i]+d-c
  else:
    heappush(Y,-c)
    dpy[N-1-i] = dpy[N-i]

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

from heapq import heappush, heappushpop
 
N = int(input())
a = list(map(int, input().split()))
 
a_list_1 = []
a_list_2 = []
for i in a[0:N]:
    heappush(a_list_1, i)
for i in list(reversed(a))[0:N]:
    heappush(a_list_2, -i)
 
sum_1 = sum(a_list_1)
sum_2 = sum(a_list_2)
sum_arr_1 = [0] * (N + 1)
sum_arr_1[0] = sum_1
sum_arr_2 = [0] * (N + 1)
sum_arr_2[-1] = sum_2
for k in range(N, 2 * N):
    l = heappushpop(a_list_1, a[k])
    sum_1 += a[k] - l
    sum_arr_1[k - N + 1] = sum_1
 
for k in reversed(range(N, 2 * N)):
    l = heappushpop(a_list_2, -a[k])
    sum_2 += -a[k] - l
    sum_arr_2[k - N] = sum_2
 
max_score = float('-inf')
for s1, s2 in zip(sum_arr_1, sum_arr_2):
    score = s1 + s2
    if score > max_score:
        max_score = score
 
print(max_score)

with open(0) as f:
    N, *a = 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)

import heapq
def main():
    N = int(input())
    A = list(map(int, input().split()))
    AH = sorted([(a, i) for i, a in enumerate(A[:2 * N])], reverse=True)
    AT = sorted(A[-N:])
    ATT = []
    for a in AT:
        heapq.heappush(ATT, -a)
    used = [False] * (2 * N)
    for _, i in AH[:N]:
        used[i] = True

    h = sum(a for a, _ in AH[:N])
    t = sum(AT)
    m = h - t
    hp = N
    for i in reversed(list(range(N, 2 * N))):
        t += A[i]
        t += heapq.heappushpop(ATT, -A[i])
        if used[i]:
            h -= A[i]
            while AH[hp][1] > i:
                hp += 1
            h += AH[hp][0]
            used[AH[hp][1]] = True
            hp += 1

        m = max(m, h - t)
    return m

print((main()))


import heapq


N = int(input())

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

lq = []
lsum = 0
rq = []
rsum = 0

for i in range(N):

    heapq.heappush(lq,a[i])
    lsum += a[i]

    heapq.heappush(rq,-1 * a[3 * N - 1 - i])
    rsum += a[3*N-1-i]

llis = []
rlis = []

for i in range(N+1):

    llis.append(lsum)
    rlis.append(rsum)

    heapq.heappush(lq,a[N+i])
    heapq.heappush(rq,-1 * a[2*N-1-i])
    lsum += a[N+i]
    rsum += a[2*N-1-i]

    lpop = heapq.heappop(lq)
    rpop = -1 * heapq.heappop(rq)
    lsum -= lpop
    rsum -= rpop

rlis.reverse()

ans = -1 * float("inf")

for i in range(N+1):

    ans = max(ans,llis[i]-rlis[i])

print (ans)

    


import copy
import heapq
N = int(input())
A = list(map(int, input().split()))

h1 = copy.deepcopy(A[:N])
x = sorted(A[N:])
h2 = x[N:]
x = x[:N]

now_w = sum(h1) - sum(x)
ans = now_w
used = []
heapq.heapify(h1)
heapq.heapify(h2)
heapq.heapify(used)

for i in range(N):
  now = A[N+i]
  heapq.heappush(h1, now)
  left = heapq.heappop(h1)
  while True:
    right_cand = heapq.heappop(h2)
    if len(used) > 0:
      x = heapq.heappop(used)
      if x == right_cand:
        continue
      else:
        heapq.heappush(used, x)
    break
      
  if right_cand >= now:
    right = right_cand
  else:
    right = now
    heapq.heappush(h2, right_cand)
    heapq.heappush(used, now)
  now_w = now_w - left + 2*now - right
  #print(ans, i, now_w, left, now, right)
  ans = max(ans, now_w)
  
print(ans)

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

import sys
from heapq import heapify, heappush, heappop

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

A1 = A[:N]
A2 = A[N:N*2]
A3 = [-a for a in A[N*2:]]
heapify(A1)
heapify(A3)

# 真ん中グループ(A2)をiまで左に取り込んだ時の左グループ(A1)の最大値
ansa = [0] * (N+1)
ansa[0] = sum(A1)
for i in range(N):
    heappush(A1, A2[i])    
    ansa[i+1] = ansa[i] + A2[i] - heappop(A1)

# 真ん中グループ(A2)を後ろからiまで右に取り込んだ時の右グループ(A1)の最小値
ansb = [0] * (N+1)
ansb[N] = -sum(A3)
for i in range(N-1, -1, -1):
    heappush(A3, -A2[i])
    ansb[i] = ansb[i+1] + A2[i] - (-heappop(A3))

# 各位置iから一番いい場所を得る
ans = -INF
for i in range(N+1):
    ans = max(ans, ansa[i]-ansb[i])
print(ans)


from heapq import heapify, heappop, heappush

N = int(input())
A = list(map(int, input().split()))
A = [-a for a in A]

L = [[a, i] for i, a in enumerate(A[:2*N])]
Sl = 0
heapify(L)
used = set()
for i in range(N):
  a, i = heappop(L)
  used.add(i)
  Sl -= a

R = A[2*N:].copy()
Sr = -sum(R)
heapify(R)

ans = Sl - Sr
for i in range(2*N-1, N-1, -1):
  a = - A[i]
  r =  - heappop(R)
  if a > r:
    heappush(R, -r)
  else:
    Sr += a - r
    heappush(R, -a)
  if i in used:
    while L:
      l, j = heappop(L)
      l *= -1
      if j < i:
        Sl += l - a
        used.add(j)
        break
  ans = max(ans, Sl - Sr)

print(ans)

import  heapq

N = int(input())
a = list(map(int, input().split()))
c_que = list(map(lambda x:x*(-1), a[2*N:]))
a_que = a[:N]

a_sum = sum(a_que)
c_sum = -sum(c_que)

heapq.heapify(a_que)
heapq.heapify(c_que)

ans = -(10**15)

score = [[0, 0] for _ in range(N+1)]
score[0][0] = a_sum
score[N][1] = c_sum

for i in range(N):
    heapq.heappush(a_que, a[N+i])
    heapq.heappush(c_que, -a[2*N-1-i])
    
    a_sum = a_sum + a[N+i] - heapq.heappop(a_que)
    c_sum = c_sum + a[2*N-1-i] + heapq.heappop(c_que)
    
    score[i+1][0] = a_sum
    score[N-1-i][1] = c_sum
    
for i in range(N+1):
    ans = max(ans, score[i][0]-score[i][1])
print(ans)

maxi=-10**99 
n=int(input())
import heapq 
l=[int(i) for i in input().split()]
k=n
sm=sum(l[0:n])
z1=[0]*(n+1)
z2=[0]*(n+1)
h=[]
z1[0]=sm 
j=1 
heapq.heapify(h)
for i in range(n):
    heapq.heappush(h,l[i])
for i in range(n,2*n):
    p=l[i]
    if p>h[0]: 
        sm+=p 
        sm-=h[0]
        heapq.heappop(h)
        heapq.heappush(h,p)
    else:
        pass 
    z1[j]=sm 
    j+=1 
sm=sum(l[2*n:3*n])
h=[]
heapq.heapify(h)
sm=0 
for i in range(2*n,3*n):
    heapq.heappush(h,-l[i])
    sm+=(l[i])
j=n 
z2[j]=sm  
j-=1 
#print(h[0])
#print(sm)
for i in range(2*n-1,n-1,-1): 
    p=-l[i]
    if p>h[0]:
        #print('jif')
        sm=sm+h[0]-p
        heapq.heappop(h)
        heapq.heappush(h,p)
        
    else:
        pass 
    z2[j]=sm 
    j-=1 
maxi=-(10**99)
#print(z1)
#print(z2)
for i in range(n+1):
    maxi=max(maxi,z1[i]-z2[i])
print(maxi)

import sys
from heapq import heapify, heappop, heappush

read = sys.stdin.read

N, *a = list(map(int, read().split()))

a1 = a[:N]
a2 = a[N:-N]
a3 = a[-N:]

left = sum(a1)
right = sum(a3)

heapify(a1)
a3 = [-i for i in a3]
heapify(a3)

b = [0] * (N + 1)
b[0] = left
for n, i in enumerate(a2, 1):
    if a1[0] < i:
        j = heappop(a1)
        left = left - j + i
        heappush(a1, i)
    b[n] = left

c = [0] * (N + 1)
c[0] = right
for n, i in enumerate(a2[::-1], 1):
    if i < -a3[0]:
        j = -heappop(a3)
        right = right - j + i
        heappush(a3, -i)
    c[n] = right
c = c[::-1]

answer = max(i - j for i, j in zip(b, c))
print(answer)


#!/usr/bin/env python3
import heapq
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, a: "List[int]"):
    h = a[:N]
    heapq.heapify(h)
    l1 = [0] * (N + 1)
    l1[0] = sum(h)
    for i in range(N):
        m = heapq.heappushpop(h, a[N + i])
        l1[i + 1] = l1[i] + a[N + i] - m
    h = [-ai for ai in a[-N:]]
    heapq.heapify(h)
    l2 = [0] * (N + 1)
    l2[N] = sum(h)
    for i in reversed(list(range(N))):
        m = heapq.heappushpop(h, -a[N + i])
        l2[i] = l2[i + 1] + (-a[N + i]) - m
    print((max(l1[i] + l2[i] for i in range(N + 1))))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(3 * N)]  # type: "List[int]"
    solve(N, a)


def __starting_point():
    main()

__starting_point()

import sys
import queue

#+++++
		
def main():
	n = int(input())
	nnn = list(map(int, input().split()))
	
	ppp=nnn[:n]
	ccc=nnn[n:2*n]
	bbb=nnn[2*n:]
	
	pp_v=[0]*(n+1)
	ppq=queue.PriorityQueue()
	for v in ppp:
		ppq.put(v)
	
	pre=sum(ppp)
	pp_v[0]=pre
	for i,v in enumerate(ccc):
		ppq.put(v)
		t=ppq.get()
		pre=pre+v-t
		pp_v[i+1]=pre
		
		
	bb_v=[0]*(n+1)
	bbq=queue.PriorityQueue()
	for v in bbb:
		bbq.put(-v)
	
	pre=-1*sum(bbb)
	bb_v[0]=pre
	for i,v in enumerate(ccc[::-1]):
		bbq.put(-v)
		t=bbq.get()
		pre=pre+(-v)-(t)
		bb_v[i+1]=pre
		
	dd=[p+q for p,q in zip(pp_v,bb_v[::-1])]
	ans=max(dd)
	
	print(ans)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

def __starting_point():
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
__starting_point()

from heapq import heappop,heappush
n=int(input())
a=list(map(int,input().split()))
p=sum(a[2*n:])
right_min=[p]
hq=[]
for i in range(2*n,2*n+n):
	heappush(hq,-a[i])
for i in range(n):
	p+=a[-n-i-1]
	heappush(hq,-a[-n-i-1])
	p+=heappop(hq)
	right_min.append(p)
l=sum(a[:n])
hq=[]
for i in range(n):
	heappush(hq,a[i])
right_min.reverse()
ans=l-right_min[0]
for i in range(n):
	l+=a[n+i]
	heappush(hq,a[n+i])
	l-=heappop(hq)
	ans=max(ans,l-right_min[i+1])
print(ans)

from heapq import heappush,heappop,heapify
n=int(input())
a=list(map(int,input().split()))
ans=-float("inf")
l=a[:n]
heapify(l)
t=sum(a[:n])
ls=[t]
for i in range(n,2*n):
    t+=a[i]
    heappush(l,a[i])
    t-=heappop(l)
    ls.append(t)
r=[-i for i in a[2*n:]]
heapify(r)
t=sum(a[2*n:])
rs=[t]
for i in range(2*n-1,n-1,-1):
    t+=a[i]
    heappush(r,-a[i])
    t+=heappop(r)
    rs.append(t)
for i in range(n+1):
    ans=max(ans,ls[i]-rs[-i-1])
print(ans)

import heapq

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

R=sorted(A[:N])
SUM1=[sum(A[:N])]
for i in range(N,2*N):
    heapq.heappush(R,A[i])
    tmp=heapq.heappop(R)
    SUM1.append(SUM1[-1]+A[i]-tmp)

B=list(map(lambda x:x*(-1),A[2*N:3*N]))
B.sort()
SUM2=[-sum(B)]
for i in range(2*N-1,N-1,-1):
    heapq.heappush(B,-A[i])
    tmp=heapq.heappop(B)
    SUM2.append(SUM2[-1]+A[i]+tmp)

ans=-float("inf")
for i in range(N+1):
    ans=max(ans,SUM1[i]-SUM2[-(i+1)])
print(ans)

from heapq import heapify, heapreplace
n = int(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)

def main():
    from heapq import heappush, heappushpop

    n = int(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)


def __starting_point():
    main()

__starting_point()

N = int(input())

A = list(map(int,input().split()))
import heapq
L = A[:N]
heapq.heapify(L)
sum_L = sum(A[:N])
L_list = []
L_list.append(sum_L)
for i in range(N):
    sum_L += A[N+i]
    heapq.heappush(L,A[N+i])
    sum_L -= heapq.heappop(L)
    L_list.append(sum_L)

A = list([-x for x in A[::-1]])
R = A[:N]
heapq.heapify(R)
sum_R = sum(A[:N])
R_list = []
R_list.append(sum_R)


for i in range(N):
    sum_R += A[N+i]
    heapq.heappush(R,A[N+i])
    sum_R -= heapq.heappop(R)
    R_list.append(sum_R)
maxi = -10000000000000000000000000000
R_list = R_list[::-1]
for i in range(N+1):
    maxi = max(maxi,L_list[i] + R_list[i])

print(maxi)


from heapq import heapify, heappushpop
import sys
sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [0] * (N+1)
    C = [0] * (N+1)
    H = [a for a in A[:N]]
    heapify(H)
    B[0] = sum(A[:N])
    for i in range(N):
        x = heappushpop(H, A[N+i])
        B[i+1] = B[i] + A[N+i] - x
    H = [-a for a in A[2*N:]]
    heapify(H)
    C[0] = sum(A[2*N:])
    for i in range(N):
        x = -heappushpop(H, -A[2*N-i-1])
        C[i+1] = C[i] + A[2*N-i-1] - x
    print(max(b-c for b,c in zip(B, C[::-1])))

def __starting_point():
    main()
__starting_point()

import heapq
def main():
    n = int(input())
    a = list(map(int, input().split()))
    q = []
    heapq.heapify(q)
    frnt = [None]*3*n
    back = [None]*3*n
    heapq.heappush(q, a[0])
    frnt[0] = a[0]
    for i in range(1, 2*n+1):
        frnt[i] = a[i]
        frnt[i] += frnt[i-1]
        heapq.heappush(q, a[i])
        if n <= i:
            frnt[i] -= heapq.heappop(q)
    q = []
    heapq.heapify(q)
    heapq.heappush(q, -1*a[3*n-1])
    back[3*n-1] = a[3*n-1]
    for i in reversed(range(n-1, 3*n-1)):
        back[i] = a[i]
        back[i] += back[i+1]
        heapq.heappush(q, -1*a[i])
        if i < 2*n:
            back[i] += heapq.heappop(q)
    ans = -float("inf")
    for i in range(n-1, 2*n):
        ans = max(ans, frnt[i] - back[i+1])
    print(ans)

def __starting_point():
    main()
__starting_point()

#!/usr/bin/env python3
import sys
import heapq

def minus(n):
    return -n

def solve(N: int, a: "List[int]"):
    ## N+iまでのリストの大きい順のNコのわ  
    left_sum = [0]*(N+1)
    heap = a[:N]
    left_sum[0] = sum(heap)
    heapq.heapify(heap)
    for i in range(N,2*N):
        heapq.heappush(heap,a[i])
        min_value = heapq.heappop(heap)
        left_sum[i-(N-1)]=left_sum[i-N]+a[i]-min_value

    b = list(map(minus,reversed(a)))
    right_sum= [0]*(N+1)
    r_heap = b[:N]
    right_sum[0] = -sum(r_heap)
    heapq.heapify(r_heap)
    for i in range(N,2*N):
        heapq.heappush(r_heap,b[i])
        min_value = heapq.heappop(r_heap)
        right_sum[i-(N-1)]=right_sum[i-N]+(-b[i])-(-min_value)
    
    answer = -10**15
    for j in range(N+1):
        answer = max(answer,left_sum[j]-right_sum[N-j])
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(3 * N)]  # type: "List[int]"
    solve(N, a)

def __starting_point():
    main()

__starting_point()

import heapq
import sys
input = sys.stdin.readline

def solve():
  n = int(input())
  a = list(int(i) for i in input().split())
  an = []
  a2n = a[n:2*n]
  a3n = []
  
  for i in range(n):
    heapq.heappush(an,a[i])
    heapq.heappush(a3n,-1*a[i+2*n])

  tmpsuman = sum(an)
  tmpsuma3n = -1*sum(a3n)
  
  suman = [tmpsuman]
  suma3n = [tmpsuma3n]
  
  for i in range(n):
    tmp = a2n[i]
    tmpsuman += tmp
    heapq.heappush(an,tmp)
    tmpsuman -= heapq.heappop(an)
    
    suman.append(tmpsuman)

    tmp = a2n[n-i-1]
    tmpsuma3n += tmp
    heapq.heappush(a3n,-1*tmp)
    tmpsuma3n -= -1*heapq.heappop(a3n)
    suma3n.append(tmpsuma3n)

  ans = -1*float("INF")
  for i in range(n+1):
    ans = max(ans,suman[i]-suma3n[n-i])
  print(ans)
solve()

import heapq

def score(init, cand):
    
    score = [0] * (n+1)
    score[0] = sum(init)
    hp = init
    heapq.heapify(hp)
    
    for i,ai in enumerate(cand):
    
        if hp[0] < ai:
            min_a = heapq.heappop(hp)
            score[i+1] = score[i] + (ai - min_a)
            heapq.heappush(hp, ai)
        else:
            score[i+1] = score[i]
    
    return score
    
n = int(input())
a = list(map(int,input().split()))
minus_a = [-x for x in a[::-1]]

former_score = score(a[:n],a[n:2*n])
latter_score = score(minus_a[:n],minus_a[n:2*n])[::-1]

ans = max(x+y for x,y in zip(former_score,latter_score))

print(ans)

import sys
from heapq import *
input = sys.stdin.readline


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

    af = a[:n]
    ab = [-v for v in a[2*n:]]
    af_sum = sum(af)
    ab_sum = -sum(ab)

    heapify(af)
    heapify(ab)
    judge = [0]*(n+1)
    judge[0] += af_sum
    judge[n] -= ab_sum
    
    for i in range(n):
        if a[n+i] > af[0]:
            af_sum -= heappop(af)
            heappush(af, a[n+i])
            af_sum += a[n+i]
        judge[i+1] += af_sum
        
        if -a[2*n-1-i] > ab[0]:
            ab_sum += heappop(ab)
            heappush(ab, -a[2*n-1-i])
            ab_sum += a[2*n-1-i]
        judge[n-1-i] -= ab_sum
    

    ans = max(judge)
    print(ans)

    
def __starting_point():
    main()

__starting_point()

import sys
from heapq import *

n, *a = map(int, sys.stdin.read().split())

def optimize(arr):
    res = arr[:n]
    heapify(res)
    sum_arr = [sum(res)]
    for x in arr[n:]:
        y = heappop(res)
        heappush(res, max(x, y))
        sum_arr.append(sum_arr[-1] + max(0, x - y))
    return sum_arr

def main():
    left = a[:n*2]
    right = [-x for x in a[n:]][::-1]

    sum_left = optimize(left)
    sum_right = optimize(right)

    res = []
    for i in range(n+1):
        res.append(sum_left[i] + sum_right[n-i])
        
    ans = max(res)
    return ans

def __starting_point():
    ans = main()
    print(ans)
__starting_point()

import heapq
N = int(input())
A = list(map(int,input().split()))
left = [sum(A[:N])]
h1 = A[:N]
heapq.heapify(h1)
for i in range(N):
    heapq.heappush(h1, A[N+i])
    temp = heapq.heappop(h1)
    left.append(left[-1] + A[N+i] - temp)
right = [sum(A[2*N:])]
h2 = list(map(lambda x: -x, A[2*N:]))
heapq.heapify(h2)
for i in range(N):
    heapq.heappush(h2, -A[2*N-1-i])
    temp = -1 * heapq.heappop(h2)
    right.append(right[-1] + A[2*N-1-i] - temp)
ans = float('-inf')
for i in range(N+1):
    ans = max(ans, left[i] - right[-(i+1)])
print(ans)

from heapq import *
n = int(input())
a = list(map(int, input().split()))

left = a[:n]
right = a[2*n:]
heapify(left)
l = [sum(left)]
r = [sum(right)]
sl = sum(left)
sr = sum(right)
for i in range(n):
    k = heappop(left)
    sl -= k
    heappush(left, max(k, a[n+i]))
    sl += max(k, a[n+i])
    l.append(sl)

right = [-i for i in right]
heapify(right)
for i in range(n):
    k = -heappop(right)
    sr -= k
    mini = min(k, a[2*n-1-i])
    heappush(right, -mini)
    sr += mini
    r.append(sr)

r.reverse()
ans = -10**15
for i in range(n+1):
    ans = max(l[i] - r[i], ans)

print(ans)


from heapq import heappush, heappop
n = int(input())
a = list(map(int, input().split()))

s1 = [0] * 3*n
pq = []
s = 0
for i in range(3*n):
    if len(pq) < n:
        s += a[i]
        heappush(pq, a[i])
        if len(pq) == n:
            s1[i] = s
    else:
        s += a[i]
        heappush(pq, a[i])
        s -= heappop(pq)
        s1[i] = s


s2 = [0] * 3*n
pq = []
s = 0
for i in reversed(list(range(3*n))):
    if len(pq) < n:
        s += a[i]
        heappush(pq, -a[i])
        if len(pq) == n:
            s2[i] = s
    else:
        s += a[i]
        heappush(pq, -a[i])
        s -= -heappop(pq)
        s2[i] = s

ans = - 10**15
for i in range(n-1, 2*n):
    ans = max(ans, s1[i] - s2[i+1])
print(ans)


import sys
import heapq

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

	left = a[0 : N]
	right = a[N*2 : N*3]

	for i in range(N):
		right[i] *= -1

	left_sum = 0
	right_sum = 0

	heap_left = []
	heap_right = []

	for i in range(N):
		left_sum += left[i]
		heapq.heappush(heap_left, left[i])
		right_sum += right[i]
		heapq.heappush(heap_right, right[i])

	temp1 = [0] * (N + 1)
	temp2 = [0] * (N + 1)

	temp1[0] = left_sum
	temp2[N] = right_sum

	for i in range(0, N):
		left_sum += a[N+i]
		heapq.heappush(heap_left, a[N+i])
		left_sum -= heapq.heappop(heap_left)
		temp1[i+1] = left_sum

	for i in range(0, N):
		right_sum -= a[N*2-1-i]
		heapq.heappush(heap_right, -a[N*2-1-i])
		right_sum -= heapq.heappop(heap_right)
		temp2[N - 1 - i] = right_sum

	ans = -100000000000000000000000000000000000000000
	for i in range(0, N + 1):
		x = temp1[i] + temp2[i]
		if(ans < x):
			ans = x
	print(ans)
main()

import heapq
n=int(input())
a=[int(i) for i in input().split()]
 
heap_left=[]
left=0
for i in range(n):
    left+=a[i]
    heapq.heappush(heap_left,a[i])
 
lst_left=[left]
for i in range(n,2*n):
    tmp=heapq.heappushpop(heap_left,a[i])
    left=left-tmp+a[i]
    lst_left+=[left]
 
heap_right=[]
right=0
for i in range(2*n,3*n):
    right+=a[i]
    heapq.heappush(heap_right,-a[i])
 
lst_right=[right]
for i in range(2*n-1,n-1,-1):
    tmp=heapq.heappushpop(heap_right,-a[i])
    right=right-(-tmp)+a[i]
    lst_right+=[right]
 

ans=-10**100
for i in range(n+1):
    ans=max(ans,lst_left[i]-lst_right[-(i+1)])
 
print (ans)

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

import heapq

lefts = a[:n]
lefts_sums = [sum(lefts)]
heapq.heapify(lefts)

for x in range(n, 2 * n):
    l = heapq.heappop(lefts)
    if l < a[x]:
        heapq.heappush(lefts, a[x])
        lefts_sums.append(lefts_sums[-1] - l + a[x])
    else:
        heapq.heappush(lefts, l)
        lefts_sums.append(lefts_sums[-1])

rights = [-_a for _a in a[2 * n:]]
rights_sums = [sum(rights)]
heapq.heapify(rights)

for x in reversed(list(range(n, 2 * n))):
    r = heapq.heappop(rights)
    if r < -a[x]:
        heapq.heappush(rights, -a[x])
        rights_sums.append(rights_sums[-1] - r - a[x])
    else:
        heapq.heappush(rights, r)
        rights_sums.append(rights_sums[-1])

rights_sums = rights_sums[::-1]
ans = -float('inf')
for i in range(len(lefts_sums)):
    ans = max(ans, lefts_sums[i] + rights_sums[i])
# print(lefts_sums, rights_sums)
print(ans)


import heapq

N = int(input())
A = list(map(int, input().split()))
l, r = [], []
ll = 0
for i in range(3*N):
    if i < N:
        heapq.heappush(l, (A[i], i))
        ll += A[i]
    else:
        heapq.heappush(r, (A[i], i))
used = set()
rr = 0
for i in range(N):
    a, idx = heapq.heappop(r)
    used.add(idx)
    rr += a
ans = ll-rr
done = set()
for i in range(N,2*N):
    done.add(i)
    if A[i] > l[0][0]:
        ll -= l[0][0]
        heapq.heappop(l)
        heapq.heappush(l, (A[i], i))
        ll += A[i]
    if i in used:
        rr -= A[i]
        a, idx = heapq.heappop(r)
        while idx in done:
            a, idx = heapq.heappop(r)
        used.add(idx)
        rr += a
    #print(i, ll, rr, l, r)
    ans = max(ans, ll-rr)
print(ans)


from heapq import heapreplace, heapify


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

dp = [0] * (N + 1)
q = A[:N]
heapify(q)
dp[0] = sum(q)
for i in range(N, 2 * N):
    a = A[i]
    if a > q[0]:
        dp[i - N + 1] += a - heapreplace(q, a)
    dp[i - N + 1] += dp[i - N]


dp2 = [0] * (N + 1)
q = [-A[i] for i in range(2 * N, 3 * N)]
heapify(q)
dp2[N] = -sum(q)
for i in range(2 * N - 1, N - 1, -1):
    a = A[i]
    if a < -q[0]:
        dp2[i - N] += a - (-heapreplace(q, -a))
    dp2[i - N] += dp2[i - N + 1]

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


import heapq
n=int(input())
l=list(map(int,input().split()))
q=[]
for i in range(n):
    heapq.heappush(q,l[i])
a1=[0]*(n+1)
a1[0]=sum(l[:n])
for i in range(n):
    p=heapq.heappop(q)
    a1[i+1]=a1[i]-p+max(p,l[i+n])
    heapq.heappush(q,max(p,l[i+n]))
#print(a1)
q=[]
l.reverse()
for i in range(n):
    heapq.heappush(q,-l[i])
a1.reverse()
a1[0]-=sum(l[:n])
z=sum(l[:n])
for i in range(n):
    p=heapq.heappop(q)
    z=z+p+min(-p,l[i+n])
    a1[i+1]-=z
    heapq.heappush(q,max(p,-l[i+n]))
print((max(a1)))


from heapq import heappop, heappush
n=int(input())
a=list(map(int,input().split()))
l=[0]*(n+1)
r=[0]*(n+1)
s=sum(a[:n])
t=sum(a[-n:])
l[0]=s
r[~0]=t
h=[]
H=[]
for i in range(n):
    heappush(h,a[i])
    heappush(H,-a[~i])
for i in range(n):
    s+=a[n+i]
    t+=a[~(n+i)]
    heappush(h,a[n+i])
    heappush(H,-a[~(n+i)])
    s-=heappop(h)
    t+=heappop(H)
    l[i+1]=s
    r[~(i+1)]=t
print(max(l[i]-r[i] for i in range(n+1)))

import heapq

N = int(input())

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

left = A[:N]
left_total = [(sum(left))]
heapq.heapify(left)

for i in range(N, 2*N):
    l = heapq.heappop(left)
    # 入れ替える場合
    if l < A[i]:
        heapq.heappush(left,A[i])
        left_total.append(left_total[-1] - l + A[i])
    # Aのある要素よりleftの最小要素の方が大きいので入れ替えない
    else:
        heapq.heappush(left,l)
        left_total.append(left_total[-1])
        

#rightもN要素から始めるが、leftとの対応のために最後にtotalをひっくり返すのを忘れない
right = [-i for i in A[2 * N:]]
right_total = [sum(right)]
heapq.heapify(right)

for i in reversed(range(N, 2*N)):
    r = heapq.heappop(right)
    if r < -A[i]:
        heapq.heappush(right, -A[i])
        right_total.append(right_total[-1] - r - A[i])
    # rの最小値の方がちいさいのでそのまま
    else:
        heapq.heappush(right, r)
        right_total.append(right_total[-1])


# left_totalとの対応のために逆にする
right_total = right_total[::-1]

ans = -float("inf")
for i in range(len(left_total)):
    ans = max(ans, left_total[i] + right_total[i])

print(ans)

import heapq

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

    left = [0] * (3 * N)
    right = [0] * (3 * N)

    tmp = 0
    q = []
    for i in range(N):
        heapq.heappush(q, a[i])
        tmp += a[i]
    left[N-1] = tmp
    for i in range(N, 2*N):
        heapq.heappush(q, a[i])
        left[i] = left[i-1] + a[i] - heapq.heappop(q)
    
    tmp = 0
    q = []
    for i in range(N*3-1, N*2-1, -1):
        heapq.heappush(q, -a[i])
        tmp += a[i]
    right[2*N] = tmp
    for i in range(2*N-1, N-1, -1):
        heapq.heappush(q, -a[i])
        right[i] = right[i+1] + a[i] + heapq.heappop(q)
    
    ans = left[N-1] - right[N]
    for i in range(N, 2*N):
        ans = max(ans, left[i]-right[i+1])
    print(ans)

def __starting_point():
    main()
__starting_point()

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

X=A[:N]
Y=[-i for i in A[2*N:]]
heapq.heapify(X)
heapq.heapify(Y)
x=sum(X)
y=-sum(Y)
XMA=[0]*(N+1)
YMI=[0]*(N+1)
XMA[0]=x
YMI[N]=y
for i in range(N):
  heapq.heappush(X,A[N+i])
  s=heapq.heappop(X)
  x+=A[N+i]-s
  XMA[i+1]=x
  
  heapq.heappush(Y,-A[2*N-1-i])
  t=-heapq.heappop(Y)
  y+=A[2*N-1-i]-t
  YMI[N-i-1]=y
  
ANS=[0]*(N+1)
for i in range(N+1):
  ANS[i]=XMA[i]-YMI[i]
print(max(ANS))

n=int(input())
a=list(map(int,input().split()))
left=[0]*(2*n+1)
right=[0]*(2*n+1)
now_a=a[:n]
left[n]=sum(now_a)
now_a.sort()
from heapq import heapify,heappop,heappush
heapify(now_a)
for i in range(n,2*n):
  if a[i]>now_a[0]:
    left[i+1]=left[i]+a[i]-now_a[0]
    heappop(now_a)
    heappush(now_a,a[i])
  else:
    left[i+1]=left[i]
b=[-x for x in a]
now_b=b[-n:]
right[n]=sum(now_b)
now_b.sort()
heapify(now_b)
for i in range(n,2*n):
  if b[-i-1]>now_b[0]:
    right[i+1]=right[i]+b[-i-1]-now_b[0]
    heappop(now_b)
    heappush(now_b,b[-i-1])
  else:
    right[i+1]=right[i]
ans=-pow(10,14)
for i in range(n+1):
  ans=max(ans,left[n+i]+right[2*n-i])
print(ans)


import heapq as hq
n = int(input())
a = list(map(int,input().split()))
x = sum(a[:n])
y = sum(a[2*n:])
fsum = [x]
lsum = [y]
hqx = a[:n]
hqy = [-a[2*n+i] for i in range(n)]
hq.heapify(hqx)
hq.heapify(hqy)
for i in range(n):
    hq.heappush(hqx,a[n+i])
    hq.heappush(hqy,-a[2*n-i-1])
    xmin = hq.heappop(hqx)
    ymax = -hq.heappop(hqy)
    fsum.append(fsum[-1]+a[n+i]-xmin)
    lsum.append(lsum[-1]+a[2*n-i-1]-ymax)
ans = -10**18
for i in range(n+1):
    ans = max(ans,fsum[i]-lsum[-i-1])
print(ans)

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

import sys
from heapq import heapify, heappush, heappop

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

A1 = A[:N]
A2 = A[N:]
sm1 = sum(A1)
sm2 = sum(A2)
que1 = []
que2 = []
S = set()
for i, a in enumerate(A1):
    que1.append((a, i))
heapify(que1)
A2 = [(a, i) for i, a in enumerate(A2, N)]
A2.sort(reverse=1)
for a, i in A2[:N]:
    sm2 -= a
    S.add(i)
    que2.append((a, i))
heapify(que2)

ans = sm1 - sm2
for i in range(N, N*2):
    # 前半
    heappush(que1, (A[i], i))
    sm1 += A[i]
    a, _ = heappop(que1)
    sm1 -= a
    # 後半
    if i not in S:
        sm2 -= A[i]
        while 1:
            a, j = heappop(que2)
            S.remove(j)
            if j > i:
                sm2 += a
                break
    ans = max(ans, sm1 - sm2)
print(ans)


n=int(input())
a=list(map(int,input().split()))
l=[0]*3*n
r=[-1000000000000000]*3*n
from heapq import heappop,heappush
h=[]
s=0
for i in a[:n]:
  heappush(h,i)
  s+=i
l[n-1]=s
for i in range(n,2*n):
  heappush(h,a[i])
  s+=a[i]
  s-=heappop(h)
  l[i]=s
h=[]
s=0
for i in a[2*n:]:
  heappush(h,-i)
  s+=-i
for i in range(2*n-1,n-2,-1):
  r[i]=s
  heappush(h,-a[i])
  s+=-a[i]
  s-=heappop(h)
print(max(l[i]+r[i]for i in range(3*n)))

# 3 N numbers
import heapq
N = int(input())
a = list(map(int, input().split()))
S = sum(a[:N])
b = a[:N]
heapq.heapify(b)
dpmax = [S for i in range(N+1)]
# dpmax[x] = 前半　ｘ + N このうちmax N　このわを記録
for i in range(N, 2*N):
    heapq.heappush(b, a[i])
    d = heapq.heappop(b)
    S += a[i]-d
    dpmax[i-N+1] = S

c = a[-N:]
for i in range(N):
    c[i] = -c[i]
T = sum(c)
heapq.heapify(c)
dpmin = [-T for i in range(N+1)]

# dpmin[x]= 後半　x + N このうち　min Nこのわを記録する
for i in range(N, 2*N):
    heapq.heappush(c, -a[-1-i])
    d = heapq.heappop(c)
    T += -a[-1-i]-d
    dpmin[i+1-N] = -T

ans = -1000000000000000000000000000000
for i in range(N+1):
    ans = max(ans, dpmax[i]-dpmin[N-i])
print(ans)

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    A = LI()
    wakeme = N
    Aleftsum = [0 for _ in range(3*N+1)]
    leftA = [x for x in A[:N]]
    heapq.heapify(leftA)
    subsum = sum(leftA)
    Aleftsum[wakeme] = subsum
    for i in range(N):
        heapq.heappush(leftA, A[wakeme + i])
        subsum += A[wakeme + i]
        subsum -= heapq.heappop(leftA)
        Aleftsum[wakeme+i+1] = subsum

    Arightsum = [0 for _ in range(3*N+1)]
    rightA = [-x for x in A[-N:]]
    heapq.heapify(rightA)
    subsum = sum(rightA)
    wakeme = 2*N
    Arightsum[wakeme] = -subsum
    for i in range(1, N+1):
        heapq.heappush(rightA, -A[wakeme-i])
        subsum -= A[wakeme - i]
        subsum -= heapq.heappop(rightA)
        Arightsum[wakeme - i] = -subsum
    ans = -inf
    for i in range(N, 2*N+1):
        ans = max(ans, Aleftsum[i] - Arightsum[i])
    print(ans)
main()



import copy
import heapq
from collections import deque
n=int(input())
left=[]
middle=deque([])
right=[]
A=list(map(int,input().split()))
for i in range(n):
  heapq.heappush(left,A[i])
c=sum(left)
for i in range(n):
  middle.append(A[n+i])
for i in range(n):
  heapq.heappush(right,A[2*n+i]*-1)
d=sum(right)
l=deque([0])
m=copy.copy(middle)
for i in range(n):
  a=left[0]
  b=m[0]
  l.append(l[-1]+max(0,b-a))
  if b-a>0:
    heapq.heapreplace(left,b)
  m.popleft()
m=copy.copy(middle)
r=deque([0])
for i in range(n):
  a=right[0]*-1
  b=m[-1]
  r.append(r[-1]+max(0,a-b))
  if a-b>0:
    heapq.heapreplace(right,b*-1)
  m.pop()
ans=0
for i in range(n+1):
  a=l[0]+r[-1]
  if a>ans:
    ans=a
  l.popleft()
  r.pop()
print(c+d+ans)

# 解説を確認、このような、最大（最小値）の出し入れが頻繁にあるデータでは、
# 「優先度付きキュー」というデータ構造を用いると容易になるようだ。
# 新規要素の Push & Pop が O(N log N) でできるとのこと。

from heapq import heapify,heappush,heappop

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

a1=a[0:n]
a_m=a[n:2*n]
a2=[ -x for x in a[2*n:3*n] ] # nega_list

a1_sums=[sum(a1)]
a2_sums=[sum(a2)]
heapify(a1)
heapify(a2)

# 左のシマに真ん中のシマを徐々に追加し、都度最小値を取り出す
for aa in a_m:
  heappush(a1,aa)
  p=heappop(a1)
  a1_sums.append(a1_sums[-1]+aa-p)

# 右のシマは都度最大値を取り出す
a_m.reverse()
for aa in a_m:
  heappush(a2,-aa)
  p=heappop(a2)
  a2_sums.append(a2_sums[-1]-aa-p)

max_val=-float("inf")
for i in range(0,n+1):
  max_val=max(max_val,a1_sums[i]+a2_sums[n-i])

print(max_val)


n = int(input())
a = list(map(int, input().split()))
b = a[n:2*n]

import heapq

q = a[:n]
heapq.heapify(q)

res = [0]*(n+1)
res[0] = sum(q)
for i, x in enumerate(b):
    heapq.heappush(q, x)
    y = heapq.heappop(q)
    res[i+1] = res[i]+x-y

b.reverse()
q = [-x for x in a[2*n:]]
heapq.heapify(q)
s = -sum(q)
res[-1] -= s

for i, x in enumerate(b):
    heapq.heappush(q, -x)
    y = heapq.heappop(q)
    s += x+y
    res[-2-i] -= s

print((max(res)))


import heapq

n=int(input())
a1=[]
b1=[]
a2=[]
b2=[]
s=input().split()
for i in range(3*n):
    if i<n:
        a1.append(int(s[i]))
    elif i>=2*n:
        b1.append(-int(s[i]))
    else:
        a2.append(int(s[i]))
        b2.append(-int(s[3*n-i-1]))
suma=[sum(a1)]
sumb=[sum(b1)]
heapq.heapify(a1)
heapq.heapify(b1)

for i in range(0,n):
    heapq.heappush(a1,a2[i])
    k=heapq.heappop(a1)
    l=suma[-1]
    suma.append(l+a2[i]-k)
for i in range(0,n):
    heapq.heappush(b1,b2[i])
    k=heapq.heappop(b1)
    l=sumb[-1]
    sumb.append(l+b2[i]-k)

ma=-1000000000000000
for i in range(n+1):
    ma=max(ma,suma[i]+sumb[-i-1])
print(ma)


n=int(input())
a=list(map(int,input().split()))
import heapq as hq
f1=[0]*(3*n)
f1[n-1]=sum(a[:n])
h=a[:n]
hq.heapify(h)
su=f1[n-1]
for i in range(n,2*n):
    cur=a[i]
    x=hq.heappop(h)
    if cur>x:
        su-=x
        su+=cur
        hq.heappush(h,cur)
    else:
        hq.heappush(h,x)
    f1[i]=su
f2=[0]*(3*n)
f2[2*n]=sum(a[2*n:])
su=f2[2*n]
h2=[]
for i in a[2*n:]:
    h2.append(-i)
hq.heapify(h2)
for i in range(2*n-1,n-1,-1):
    cur=a[i]
    x=-1*hq.heappop(h2)
    if cur<x:
        su-=x
        su+=cur
        hq.heappush(h2,-cur)
    else:
        hq.heappush(h2,-x)
    f2[i]=su
ans=-float('inf')
for i in range(n-1,2*n):
    ans=max(ans,f1[i]-f2[i+1])
print(ans)





from heapq import heappush, heapreplace


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

dp = [0] * (N + 1)
q = []
cnt = 0
for i in range(N):
    a = A[i]
    heappush(q, a)
    cnt += a
dp[0] = cnt
for i in range(N, 2 * N):
    a = A[i]
    if a > q[0]:
        cnt += a - heapreplace(q, a)
    dp[i - N + 1] = cnt


dp2 = [0] * (N + 1)
q = []
cnt = 0
for i in range(2 * N, 3 * N):
    a = A[i]
    heappush(q, -a)
    cnt += a
dp2[N] = cnt
for i in range(2 * N - 1, N - 1, -1):
    a = A[i]
    if a < -q[0]:
        cnt += a - (-heapreplace(q, -a))
    dp2[i - N] = cnt

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


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

h = a[:n]
heapq.heapify(h)
first = [0] * (n+1)
s = sum(a[:n])
first[0] = s
for i in range(n):
    s += a[n+i]
    heapq.heappush(h, a[n+i])
    s -= heapq.heappop(h)
    first[i+1] = s

h = list(map(lambda x: -x, a[2*n:]))
heapq.heapify(h)
second = [0] * (n+1)
s = - sum(a[2*n:])
second[0] = s
for i in range(n):
    s -= a[2*n - i - 1]
    heapq.heappush(h, -a[2*n - i - 1])
    s -= heapq.heappop(h)
    second[i+1] = s

ans = - 10 ** 18
for i in range(n+1):
    ans = max(ans, first[i] + second[n-i])
print(ans)

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

import heapq

lefts = a[:n]
lefts_sums = [sum(lefts)]
heapq.heapify(lefts)

for x in range(n, 2 * n):
    l = heapq.heappop(lefts)
    if l < a[x]:
        heapq.heappush(lefts, a[x])
        lefts_sums.append(lefts_sums[-1] - l + a[x])
    else:
        heapq.heappush(lefts, l)
        lefts_sums.append(lefts_sums[-1])

rights = [-_a for _a in a[2 * n:]]
rights_sums = [sum(rights)]
heapq.heapify(rights)

for x in reversed(list(range(n, 2 * n))):
    r = heapq.heappop(rights)
    if r < -a[x]:
        heapq.heappush(rights, -a[x])
        rights_sums.append(rights_sums[-1] - r - a[x])
    else:
        heapq.heappush(rights, r)
        rights_sums.append(rights_sums[-1])

rights_sums = rights_sums[::-1]
ans = -float('inf')
for i in range(len(lefts_sums)):
    ans = max(ans, lefts_sums[i] + rights_sums[i])
# print(lefts_sums, rights_sums)
print(ans)


import heapq

# d = [8, 2, 2, 7, 4, 6, 5, 3, 8]

N = int(input())
d = list(map(int, input().split()))
d_rev = d[::-1]

d1 = d[:N]
heapq.heapify(d1)
d2 = [-i for i in d_rev[:N]]
heapq.heapify(d2)
sum_d1 = sum(d1)
sum_d2 = sum(d2)

sum_d1_arr = [sum_d1]
sum_d2_arr = [sum_d2]

for k in range(N, 2 * N):
    c = sum_d1_arr[-1]
    c += d[k]
    n = heapq.heappushpop(d1, d[k])
    c -= n
    sum_d1_arr.append(c)

    e = sum_d2_arr[-1]
    e += -d_rev[k]
    n = heapq.heappushpop(d2, -1 * d_rev[k])
    e -= n
    sum_d2_arr.append(e)

print(max(v+w for v, w in zip(sum_d1_arr, sum_d2_arr[::-1])))

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    A = LI()
    wakeme = N
    Aleftsum = [0 for _ in range(3*N+1)]
    Arightsum = [0 for _ in range(3*N+1)]

    leftA = [x for x in A[:N]]
    rightA = [-x for x in A[-N:]]

    heapq.heapify(leftA)
    heapq.heapify(rightA)

    lsum = sum(leftA)
    rsum = sum(rightA)

    Aleftsum[wakeme] = lsum
    Arightsum[2*N] = -rsum

    # [0, N)から[0, 2N)までの和が欲しい
    # Aleftsum(i): [0, i)までの上位N個の和

    # [2N, 3N)から[N, 3N)までの和が欲しい
    # Arightsum(i): [i, 3N)までの上位N個の和

    for i in range(N):
        # [0, N+1)から[0, 2N)までやる。
        # [0, wakeme + i + 1)の和を計算する。
        # wakeme=Nなので、wakeme + i + 1 = 2N -> i = N - 1
        newl = A[wakeme + i]
        lsum += newl
        lsum -= heapq.heappushpop(leftA, newl)
        Aleftsum[wakeme+i+1] = lsum

        # [2N-1, 3N)から[N, 3N)までやる。
        # r_wakeme = 2N-1として、
        # r_wakeme - i = 2N - 1 -> i=0
        # r_wakeme - i = N -> i=N-1
        newr = A[2*N-1 - i]
        rsum -= newr
        rsum -= heapq.heappushpop(rightA, -newr)
        Arightsum[2*N-1 - i] = -rsum

    ans = -inf
    for i in range(N, 2*N+1):
        ans = max(ans, Aleftsum[i] - Arightsum[i])

    print(ans)
main()



from heapq import heappush, heappop
n = int(input())
a = list(map(int, input().split()))
max_sum_fh = [0] * (n + 1)
min_sum_lh = [0] * (n + 1)
 
hq_fh = []
hq_lh = []
 
for i in range(n):
    heappush(hq_fh, a[i])
    heappush(hq_lh, -a[-1 - i])

max_sum_fh[0] = sum(hq_fh)
min_sum_lh[n] = -sum(hq_lh)

for i in range(n):
    if a[i + n] > hq_fh[0]:
        value_in = a[i + n]
        value_out = heappop(hq_fh)
        heappush(hq_fh, value_in)
        max_sum_fh[i + 1] = max_sum_fh[i] - value_out + value_in
    else:
        max_sum_fh[i + 1] = max_sum_fh[i]
    if -a[-1 - i - n] > hq_lh[0]:
        value_in = -a[-1 - i - n]
        value_out = heappop(hq_lh)
        heappush(hq_lh, value_in)
        min_sum_lh[-2 - i] = min_sum_lh[-1 - i] + value_out - value_in
    else:
        min_sum_lh[-2 - i] = min_sum_lh[-1 - i]
    
print((max([max_sum_fh[i] - min_sum_lh[i] for i in range(n + 1)])))


import heapq


def solve(n):
  a = list(map(int,input().split()))
  # 左半分を計算して右端[n+idx]でメモ
  # 左半分は最大化したいので最小値が初めに出てくるようにする
  leftHsum = [0 for i in range(n+1)]
  leftH = a[0:n]
  heapq.heapify(leftH)
  leftHsum[0] = sum(leftH) # 
  for i in range(n):
    if leftH[0] < a[n+i]:
      leftHsum[i+1] = leftHsum[i] - leftH[0] + a[n+i]
      heapq.heappop(leftH)
      heapq.heappush(leftH, a[n+i])
    else:
      leftHsum[i+1] = leftHsum[i]
  # 右半分は負の値で保持する
  # もっとも大きい値から追い出していく
  rightHsum = [0 for i in range(n+1)]
  rightH = list([-x for x in a[2*n:3*n]])
  heapq.heapify(rightH)
  rightHsum[0] = - sum(rightH)
  for i in range(n):
    if rightH[0] < -a[2*n-i-1]:
      rightHsum[i+1] = rightHsum[i] + rightH[0] + a[2*n-i-1]
      heapq.heappop(rightH)
      heapq.heappush(rightH, -a[2*n-i-1])
    else:
      rightHsum[i+1] = rightHsum[i]
  result = -1000000000000000000
  #print(leftHsum)
  #print(rightHsum)
  for i in range(n+1):
    result = max(result, leftHsum[0+i]-rightHsum[n-i])
  return result





n = int(input())
print((solve(n)))


#!/usr/bin/env python3
import sys
INF = float("inf")
from collections import deque

import heapq


class MaxHeap(object):
    def __init__(self, x):
        self.heap = [-e for e in x]
        heapq.heapify(self.heap)

    def push(self, value):
        heapq.heappush(self.heap, -value)

    def pop(self):
        return -heapq.heappop(self.heap)


class MinHeap(object):
    def __init__(self, x):
        self.heap = [e for e in x]
        heapq.heapify(self.heap)

    def push(self, value):
        heapq.heappush(self.heap, value)

    def pop(self):
        return heapq.heappop(self.heap)


def solve(N: int, a: "List[int]"):

    mae = MinHeap(a[:N])
    mae_tot = [sum(a[:N])]
    for curr in range(N, 2*N):
        mae.push(a[curr])
        mmin = mae.pop()
        mae_tot.append(mae_tot[-1]+a[curr]-mmin)

    ushiro = MaxHeap(a[2*N:])
    ushiro_tot = [sum(a[2*N:])]
    for curr in range(2*N-1, N-1, -1):
        ushiro.push(a[curr])
        umax = ushiro.pop()
        ushiro_tot.append(ushiro_tot[-1]+a[curr]-umax)

    m = -INF
    for mt, ut in zip(mae_tot, reversed(ushiro_tot)):
        m = max(m, mt-ut)
    print(m)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(3*N)]  # type: "List[int]"
    solve(N, a)


def __starting_point():
    main()

__starting_point()