Problem:
 Score : 500 points    Problem Statement 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 1 2
3 1 4 1 5 9      Sample Output 1 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 .       Sample Input 2 1
1 2 3      Sample Output 2 -1  For example, when a_1 are removed, a' will be (2, 3) , which has a score of 2 - 3 = -1 .       Sample Input 3 3
8 2 2 7 4 6 5 3 8      Sample Output 3 5  For example, when a_2 , a_3 and a_9 are removed, a' will be (8, 7, 4, 6, 5, 3) , which has a score of (8 + 7 + 4) - (6 + 5 + 3) = 5 .

Solution (Python):
def examD():
    N = I()
    a = LI()
    a_b = list(map(lambda x: x*(-1), a))
    R = a[:N]; B = a_b[2*N:]
    heapq.heapify(R)
    heapq.heapify(B)
    ansC =[]
    curR = [sum(R)]; curB = [-sum(B)]
    for i in range(N):
        heapq.heappush(R, a[N+i])
        cur = curR[-1] - heapq.heappop(R) + a[N+i]
        curR.append(cur)
    for i in range(N):
        heapq.heappush(B, a_b[2*N-1-i])
        cur =curB[-1] - heapq.heappop(B)*(-1) - a_b[2*N-1-i]
        curB.append(cur)
    for i in range(N+1):
        ansC.append(curR[i]-curB[-1-i])
    ans = max(ansC)
    print(ans)




import sys
import copy
import bisect
import heapq
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Solution (Python):
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)

Solution (Python):
import heapq

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

big_a = []  
for i in range(n):
    heapq.heappush(big_a,a[i])

small_a = []  
for i in range(n):
    heapq.heappush(small_a,-a[3*n-1-i])  

now_big = sum(big_a)
now_small = -sum(small_a)
big_data = [now_big]  
small_data = [now_small]  

for k in range(n):
    
    heapq.heappush(big_a, a[k+n])
    now_big += a[k+n] - heapq.heappop(big_a)  
    big_data.append(now_big)

    
    heapq.heappush(small_a, -a[2*n-1-k])
    now_small += a[2*n-1-k] + heapq.heappop(small_a)  
    small_data.append(now_small)



ans = -10**18
for k in range(n+1):
    ans = max(ans, big_data[k]-small_data[n-k])

print(ans)

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

big_a = []
for i in range(n):
    heapq.heappush(big_a,a[i])

small_a = []
for i in range(n):
    heapq.heappush(small_a,-a[3*n-1-i])

now_big = sum(big_a)
now_small = -sum(small_a)
big_data = [now_big]
small_data = [now_small]

for k in range(n):
    now_big += a[k+n]
    heapq.heappush(big_a,a[k+n])
    now_big -= heapq.heappop(big_a)
    big_data.append(now_big)

    now_small += a[2*n-1-k]
    heapq.heappush(small_a,-a[2*n-1-k])
    now_small += heapq.heappop(small_a)
    small_data.append(now_small)
    



ans = -10**18
for k in range(n+1):
    ans = max(ans,big_data[k]-small_data[n-k])

print(ans)

Solution (Python):
import heapq

class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq) * self.sign

    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)

    def top(self):
        return self.hq[0] * self.sign


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

heap_l = Heapq(A[:n])
heap_r = Heapq(A[2*n:],desc=True)

max_l = [0]*(n+1)
min_r = [0]*(n+1)
max_l[0] = sum(A[:n])
min_r[0] = sum(A[2*n:])

for i in range(n):
    p = heap_l.pop()
    heap_l.push(max(A[n+i],p))
    max_l[i+1] = max_l[i]+max(0,A[n+i]-p)

    q = heap_r.pop()
    heap_r.push(min(A[-1-i-n],q))
    min_r[i+1] = min_r[i]+min(0,A[-1-i-n]-q)

ans = -float('inf')

for i in range(n+1):
    ans = max(ans,max_l[i]-min_r[-1-i])

print(ans)

Solution (Python):
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 


for i in range(2*n-1,n-1,-1): 
    p=-l[i]
    if p>h[0]:
        
        sm=sm+h[0]-p
        heapq.heappop(h)
        heapq.heappush(h,p)
        
    else:
        pass 
    z2[j]=sm 
    j-=1 
maxi=-(10**99)


for i in range(n+1):
    maxi=max(maxi,z1[i]-z2[i])
print(maxi)

Solution (Python):
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)

Solution (Python):


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 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)


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)


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))


ans = -INF
for i in range(N+1):
    ans = max(ans, ansa[i]-ansb[i])
print(ans)

Solution (Python):
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))

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

pre = sum(a[:n])
post = -sum(a[2*n:])
post2 = post
ans = - pre + post

Q = []
for i in range(n):
    heapq.heappush(Q, a[i])

S_pre = [pre]

for i in range(n,2*n):
    pre += a[i]
    heapq.heappush(Q,a[i])
    q = heapq.heappop(Q)
    pre -= q
    S_pre.append(pre)

Q2 = []
for i in range(2*n,3*n):
    heapq.heappush(Q2, -a[i])
S_post = [post]
for i in range(2*n - 1,n-1,-1):
    post -= a[i]
    heapq.heappush(Q2,-a[i])
    q = heapq.heappop(Q2)
    
    post -= q
    S_post.append(post)



for i in range(n+1):
    ans = max(ans, S_pre[n-i]+S_post[i])
print(ans)

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
frontheap,backheap = [],[]
front,back = [],[]
f,b = 0,0
for i in range(n):
    heappush(frontheap,a[i])
    f += a[i]
    heappush(backheap,-a[-i-1])
    b += a[-i-1]
front.append(f)
back.append(b)
for i in range(n):
    x = heappop(frontheap)
    heappush(frontheap,max(x,a[n+i]))
    front.append(front[-1] - x + max(x,a[i+n]))
    y = heappop(backheap)
    heappush(backheap,-min(-y,a[2*n-i-1]))
    back.append(back[-1] + y + min(-y,a[2*n-i-1]))
ans = -inf
for i in range(n+1):
    ans = max(ans,front[i] - back[-i-1])
print(ans)

Solution (Python):
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)

Solution (Python):
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)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
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)

Solution (Python):
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)))

Solution (Python):
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


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):
    
    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
    
    ans = max(ans, ans0)


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


ans = max(ans, saigo)

print(ans)

Solution (Python):
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)]))

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
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)

if __name__ == "__main__":
    main()

Solution (Python):
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(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)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    x, y = LI()
    a = [1, 3, 5, 7, 8, 10, 12]
    b = [4, 6, 9, 11]
    c = [2]
    if x in a and y in a:
        print("Yes")
        return
    if x in b and y in b:
        print("Yes")
        return
    if x in c and y in c:
        print("Yes")
        return
    print("No")
    return


def B():
    h, w = LI()
    print("
    for _ in range(h):
        a = ["
        for s in S():
            a.append(s)
        a.append("
        print("".join(a))
    print("
    return


def C():
    h, w = LI()
    ans = inf
    for i in range(1, h):
        ans = min(ans, max(i * w, (h - i) * (w // 2), (h - i) * (w - w // 2)) - min(i * w, (h - i) * (w // 2), (h - i) * (w - w // 2)))
        ans = min(ans, max(i * w, (h - i) // 2 * w, (h - i - (h - i) // 2) * w) - min(i * w, (h - i) // 2 * w, (h - i - (h - i) // 2) * w))
    h, w = w, h
    for i in range(1, h):
        ans = min(ans, max(i * w, (h - i) * (w // 2), (h - i) * (w - w // 2)) - min(i * w, (h - i) * (w // 2), (h - i) * (w - w // 2)))
        ans = min(ans, max(i * w, (h - i) // 2 * w, (h - i - (h - i) // 2) * w) - min(i * w, (h - i) // 2 * w, (h - i - (h - i) // 2) * w))
    print(ans)
    return






def D():
    n = II()
    a = LI()
    first_half_list = []
    final_half_list = []
    first_half_sum = deque([0])
    final_half_sum = deque([0])
    ans = -inf
    for i in range(n):
        heappush(first_half_list, a[i])
        first_half_sum[0] += a[i]
        heappush(final_half_list, -a[-i - 1])
        final_half_sum[0] -= a[-i - 1]
    for i in range(1, n + 1):
        q = heappop(first_half_list)
        heappush(first_half_list, max(q, a[i + n - 1]))
        first_half_sum.append(first_half_sum[-1] - q + max(q, a[i + n- 1]))
        q = heappop(final_half_list)
        heappush(final_half_list, max(q, -a[-n - i]))
        final_half_sum.appendleft(final_half_sum[0] - q + max(q, -a[-n - i]))
    for i in range(n + 1):
        ans = max(ans, first_half_sum[i] + final_half_sum[i])
    print(ans)
    return



if __name__ == '__main__':
    D()

Solution (Python):
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)

Solution (Python):

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))  
    a = [int(next(tokens)) for _ in range(3*N)]  
    solve(N, a)


if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappush, heappop, heapify
import sys
input = sys.stdin.readline

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

dpl = [0] * (N * 3)
dpr = [0] * (N * 3)
l = [a[i] for i in range(N)]
r = [-a[i] for i in range(2*N, 3*N)]
heapify(l)
heapify(r)

dpl[N-1] = sum(l)
for i in range(N, 2*N) :
    heappush(l, a[i])
    m = heappop(l)
    dpl[i] = dpl[i-1] + a[i] - m
    
dpr[2*N] = -sum(r)
for i in range(2*N-1, N-1, -1) :
    heappush(r, -a[i])
    M = heappop(r)
    dpr[i] = dpr[i+1] + a[i] + M

M = -float('inf')
for i in range(N-1, 2*N) :
    M = max(M, dpl[i]-dpr[i+1])
print(M)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
N = int(input())
*A, = map(int,input().split())

from heapq import *

B1 = []
hpu = heappush
hpp = heappushpop
for a in A[:N]:
    hpu(B1,a)
S1 = [sum(B1)]
for a in A[N:2*N]:
    S1.append(S1[-1]+ a - hpp(B1,a))
B2 = []
for a in A[2*N:]:
    hpu(B2,-a)
S2 = [-sum(B2)]
for a in A[N:2*N][::-1]:
    S2.append(S2[-1] + a + hpp(B2,-a))

print(max(S1[i]-S2[-i-1] for i in range(N+1)))

Solution (Python):
from heapq import heappop, heappush

inf = float('inf')

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



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)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007



"""
x,y = LI()
f = [0,1,2,1,3,1,3,1,1,3,1,3,1]
if f[x] == f[y]:
    print("Yes")
else:
    print("No")
"""

"""
h,w = LI()
a = SR(h)
print("
for i in range(h):
    print("
    for j in a[i]:
        print(j,end = "")
    print("
print("
"""

"""
h,w = LI()
ans = float("inf")
x = w//2
y = h//2
if not w%2:
    for i in range(1,h):
        if (h-i)%2 == 0:
            ans = min(ans,abs(w*i-w*(h-i)//2))
        ans = min(ans,abs(w*i-x*(h-i)))
else:
    for i in range(1,h):
        if (h-i)%2 == 0:
            ans = min(ans,abs(w*i-w*(h-i)//2))
        if w*i < x*(h-i):
            ans = min(ans,abs(w*i-(x+1)*(h-i)))
        elif w*i < (x+1)*(h-i):
            ans = min(ans,h-i)
        else:
            ans = min(ans,abs(w*i-x*(h-i)))
if not h%2:
    for i in range(1,w):
        if (w-i)%2 == 0:
            ans = min(ans,abs(h*i-h*(w-i)//2))
        ans = min(ans,abs(h*i-y*(w-i)))
else:
    for i in range(1,w):
        if (w-i)%2 == 0:
            ans = min(ans,abs(h*i-h*(w-i)//2))
        if h*i < y*(w-i):
            ans = min(ans,abs(h*i-(y+1)*(w-i)))
        elif h*i < (y+1)*(w-i):
            ans = min(ans,w-i)
        else:
            ans = min(ans,abs(h*i-y*(w-i)))
print(ans)
"""


n = I()
a = LI()
q = []
s = 0
for i in range(n):
    heappush(q,a[i])
    s += a[i]
fl = [s]

for i in range(n,2*n):
    heappush(q,a[i])
    s -= heappop(q)
    s += a[i]
    fl.append(s)
q = []
s = 0
for i in range(2*n,3*n)[::-1]:
    heappush(q,-a[i])
    s += a[i]
fr = [s]

for i in range(n,2*n)[::-1]:
    heappush(q,-a[i])
    s += heappop(q)
    s += a[i]
    fr.append(s)
print(max(list(map(lambda x: x[0]-x[1], zip(fl,fr[::-1])))))

Solution (Python):
import heapq

def main():
    num = int(input())
    data = list(map(int, input().split()))

    left_heap = []
    left_sum = 0
    for i in range(num):
        left_sum += data[i]
        heapq.heappush(left_heap, data[i])

    dp_left = [0 for i in range(num + 1)]
    dp_left[0] = left_sum

    for i in range(num):
        now_num = data[num + i]
        pop_data = heapq.heappushpop(left_heap, now_num)
        left_sum += now_num - pop_data
        dp_left[i + 1] = left_sum

    right_heap = []
    right_sum = 0
    for i in range(num):
        right_sum += data[3 * num - 1 - i]
        heapq.heappush(right_heap, -data[3 * num - 1 - i])

    dp_right = [0 for i in range(num + 1)]
    dp_right[0] = right_sum

    for i in range(num):
        now_num = data[2 * num - 1 - i]
        pop_data = heapq.heappushpop(right_heap, -now_num)
        right_sum += now_num + pop_data
        dp_right[i + 1] = right_sum
    dp_right = dp_right[::-1]

    ans = dp_left[-1] - dp_right[-1]
    for i in range(num):
        ans = max(ans, dp_left[i] - dp_right[i])

    print(ans)

if __name__ == '__main__':
    main()