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):
from heapq import heappop, heappush, heapify

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

L = A[:N]
heapify(L)
sumL = [sum(A[:N])]

for i in range(N):
    x = heappop(L)
    if x < A[N + i]:
        sumL.append(sumL[-1] - x + A[N + i])
        heappush(L, A[N + i])
    else:
        sumL.append(sumL[-1])
        heappush(L, x)

R = list(map(lambda x: -x, A[2 * N:]))
heapify(R)
sumR = [sum(A[2 * N:])]

for i in range(N):
    x = -heappop(R)
    if x > A[2 * N - 1 - i]:
        sumR.append(sumR[-1] - x + A[2 * N - 1 - i])
        heappush(R, -A[2 * N - 1 - i])
    else:
        sumR.append(sumR[-1])
        heappush(R, -x)

res = -10**18

for i in range(N + 1):
    res = max(res, sumL[i] - sumR[-1 - i])

print(res)

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

    
    

    
    

    for i in range(N):
        
        
        
        newl = A[wakeme + i]
        lsum += newl
        lsum -= heapq.heappushpop(leftA, newl)
        Aleftsum[wakeme+i+1] = lsum

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

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

Solution (Python):

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
import heapq

def main():
    mod=10**9+7
    N=I()
    a=LI()
    q1=a[:N]
    s1=[0]*(N+1)
    s1[0]=sum(q1)
    heapq.heapify(q1)
        
    q2=[]
    heapq.heapify(q2)
    s2=[0]*(N+1)
    for i in range(N):
        b=a[-1-i]*(-1)
        s2[0]+=b
        heapq.heappush(q2,b)
    
    
    for i in range(N):
        bb=a[i+N]
        heapq.heappush(q1,bb)
        b=heapq.heappop(q1)
        s1[i+1]=s1[i]+bb-b
        
        cc=a[-1-N-i]*(-1)
        heapq.heappush(q2,cc)
        c=heapq.heappop(q2)
        s2[i+1]=s2[i]+cc-c
        
    L=[0]*(N+1)
    ans=-1*10**16
    for i in range(N+1):
        temp=s1[i]+s2[-1-i]
        if ans<temp:
            ans=temp
    print(ans)
        
        
    

main()

Solution (Python):
import heapq
N = int(input())
A = list(map(int,input().split()))
Af = A[:N]
Ab = [-i for i in A[2*N:]]
asum = sum(Af)
bsum = -sum(Ab)
bsum2 = -sum(Ab)
heapq.heapify(Af)
heapq.heapify(Ab)
flist = [sum(Af)]
blist = []
for i in range(N,2*N):
    mina = heapq.heappop(Af)
    if A[i] > mina:
        asum = asum -mina + A[i]
        flist.append(asum)
        heapq.heappush(Af,A[i])        
    else:
        flist.append(asum)
        heapq.heappush(Af,mina)
    
for i in range(2*N-1,N-1,-1):
    maxa = heapq.heappop(Ab)
    if (-A[i]) > maxa:
        bsum2 = bsum2 + maxa +A[i]
        blist.append(bsum2)
        heapq.heappush(Ab,-A[i])
    else:
        blist.append(bsum2)
        heapq.heappush(Ab,maxa)    
blist = blist[::-1]
ans = []
blist.append(bsum)
for i in range(N+1):
    ans.append(flist[i]-blist[i])
print(max(ans))

Solution (Python):
import heapq
import bisect
n = int(input())
a = list(map(int, input().split()))
first_que = [a[i] for i in range(n)]
first_sum = sum(first_que)
heapq.heapify(first_que)
latter_que = [a[i] * -1 for i in range(2*n,3*n)]
latter_sum = sum(latter_que) * -1
heapq.heapify(latter_que)
ans = [0 for i in range(n+1)]
ans[0] = first_sum
for i in range(n,2*n):
    heapq.heappush(first_que, a[i])
    p = heapq.heappop(first_que)
    first_sum += (a[i] - p)
    ans[i-n+1] = first_sum
ans[-1] -= latter_sum

for i in range(2*n-1,n-1,-1):
    heapq.heappush(latter_que,a[i]*(-1))
    p = heapq.heappop(latter_que) * (-1)
    latter_sum += (a[i] - p)
    ans[i-n] -= latter_sum
print(max(ans))

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

maxL=[]
l=[]
for i in range(n):
  l.append(a[i])
s=sum(l)
maxL.append(s)
heapq.heapify(l)
for i in range(n,2*n):
  heapq.heappush(l,a[i])
  s+=a[i]
  s-=heapq.heappop(l)
  maxL.append(s)

minL=[]
l2=[]
for i in range(2*n,3*n):
  l2.append(-a[i])
s2=sum(l2)
minL.append(s2*(-1))
heapq.heapify(l2)
for i in range(2*n-1,n-1,-1):
  heapq.heappush(l2,-a[i])
  s2-=a[i]
  s2-=heapq.heappop(l2)
  minL.append(s2*(-1))

minL.reverse()
ans=[]
for i in range(n+1):
  ans.append(maxL[i]-minL[i])
print(max(ans))

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

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

Solution (Python):
import heapq
n = int(input())
a = list(map(int, input().split()))
p = [0] * (n + 1)
hq = a[:n]
heapq.heapify(hq)
for i in range(n, 2 * n):
    heapq.heappush(hq, a[i])
    p[i + 1 - n] = heapq.heappop(hq) + p[i - n]
q = [0] * (n + 1)
hq = list(map(lambda x: -x, a[2 * n:]))
heapq.heapify(hq)
for i in range(2 * n, n, -1):
    heapq.heappush(hq, -a[i - 1])
    q[i - 1 - n] = -heapq.heappop(hq) + q[i - n]
s = sum(a[:n])
t = sum(a[n:])
ans = -float('inf')
for i in range(n + 1):
    ans = max(ans, s - t + q[i] - p[i])
    s += a[n + i]
    t -= a[n + i]
print(ans)

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

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

Solution (Python):
import sys
from heapq import heapify, heappop, heappush

read = sys.stdin.read

N, *a = 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)

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

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

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

if __name__ == "__main__":
    main()

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

Solution (Python):
import heapq



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

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

Solution (Python):
def main():
    from heapq import heappush, heappushpop

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

    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])  
    print(ret)


if __name__ == '__main__':
    main()

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

s=a[:n]
m=a[n:2*n]
f=a[2*n:]

ssum=sum(s)
fsum=sum(f)

import heapq

heapq.heapify(s)
ms=[0]*n
mf=[0]*n

for i in range(n):
    heapq.heappush(s,m[i])
    mn=heapq.heappop(s)
    ms[i]=mn

for i in range(n):
    f[i]*=-1
heapq.heapify(f)

for i in range(n-1,-1,-1):
    heapq.heappush(f,-m[i])
    mx=-heapq.heappop(f)
    mf[i]=mx


srui=[0]*(n+1)
srui[0]=ssum
for i in range(n):
    srui[i+1]=srui[i]-ms[i]+m[i]

frui=[0]*(n+1)
frui[-1]=fsum

for i in range(n,0,-1):
    frui[i-1]=frui[i]-mf[i-1]+m[i-1]


ans=-float("inf")
for i in range(n+1):
    ans=max(ans,srui[i]-frui[i])
print(ans)

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

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

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

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

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

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

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

Solution (Python):
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])
    
    else:
        heapq.heappush(left,l)
        left_total.append(left_total[-1])
        


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])
    
    else:
        heapq.heappush(right, r)
        right_total.append(right_total[-1])



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)

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

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

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):

import sys
import heapq

def minus(n):
    return -n

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

if __name__ == '__main__':
    main()

Solution (Python):
import heapq

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

a1 = a[:n]
s1 = []
ts = sum(a1)
s1.append(ts)

heapq.heapify(a1)
for i in range(n,n*2):
    ts += a[i]
    heapq.heappush(a1,a[i])
    ts -= heapq.heappop(a1)
    s1.append(ts)

a2 = a[(n*2):]
a2 = list(map(lambda x: x*(-1), a2)) 
s2 = []
ts = sum(a2)
s2.append(ts)

heapq.heapify(a2)
for i in range(n*2-1,n-1,-1):
    ts -= a[i]
    heapq.heappush(a2,a[i] * -1)
    ts -= heapq.heappop(a2)
    s2.append(ts)

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

Solution (Python):
import heapq

n = int(input())
num = [ int(v) for v in input().split() ]

left_list = num[:n]
right_list = [ -i for i in num[2*n:] ]
left_list.sort()
right_list.sort()
sl, sr = sum(left_list), sum(right_list)
sum_left_list = [sl]
sum_right_list = [sr]

for p in num[n:2*n]:
    q = heapq.heappop(left_list)
    if p > q:
        sl += (p-q)
        heapq.heappush(left_list, p)
    else:
        heapq.heappush(left_list, q)
    sum_left_list.append(sl)

for p in num[2*n-1:n-1:-1]:
    p *= -1
    q = heapq.heappop(right_list)
    if p > q:
        sr += (p-q)
        heapq.heappush(right_list, p)
    else:
        heapq.heappush(right_list, q)
    sum_right_list.append(sr)

sum_right_list.reverse()
ans_list = [ sum_left_list[i] + sum_right_list[i] for i in range(n+1) ]
print(max(ans_list))

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

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

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

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 sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
from heapq import heapify,heappop,heappush
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    P=[None]*(n+1); S=[None]*(n+1)

    
    Q=A[:n]
    P[0]=sum(Q)
    heapify(Q)
    for i in range(1,n+1):
        a=heappop(Q)
        b=A[n+i-1]
        P[i]=P[i-1]-a+max(a,b)
        heappush(Q,max(a,b))

    
    Q=[-a for a in A[2*n:]]
    S[-1]=sum(Q)
    heapify(Q)
    for i in range(n-1,-1,-1):
        a=heappop(Q)
        b=-A[n+i]
        S[i]=S[i+1]-a+max(a,b)
        heappush(Q,max(a,b))

    print(max(*(p+s for p,s in zip(P,S))))
resolve()

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

Solution (Python):

import sys, math, heapq,copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans=count=0


ans = -inf
n = int(input())
A = list(map(int, input().split()))
AL, AR = A[:n], A[2*n:]
al,ar=copy.copy(AL),copy.copy(AR)
AN = A[n:2*n]
LS, RS = sum(AL), sum(AR)
AR = list(map(lambda ddd: -ddd, AR))
heapq.heapify(AL)
heapq.heapify(AR)
tmp=LS
ANSR=[0]*n
ANSL=[0]*n

for i in range(n):
    if AN[i]-AL[0] >0:
        LS = LS-heapq.heappop(AL)+AN[i]
        heapq.heappush(AL,AN[i])
    ANSL[i] = LS

LS=tmp
for j in range(n-1,-1,-1):
    if 0 < -AR[0]-AN[j]:
        RS = RS+heapq.heappop(AR)+AN[j]
        heapq.heappush(AR,-AN[j])
    ANSR[j] = RS
ANSR=ANSR+[sum(ar)]
ANSL=[sum(al)]+ANSL
for i in range(n+1):
    ans=max(ans,ANSL[i]-ANSR[i])
print(ans)