def C():
from collections import defaultdict
N = int(input())
(*A,) = map(int, input().split())
num_idx = defaultdict(list)
for i, a in enumerate(A):
num_idx[a].append(i)
_, ans = zip(*sorted([[idx[1], n] for n, idx in num_idx.items()]))
print(*ans)test_all(C)
from heapq import *
from collections import defaultdict
class my_heapq:
def __init__(self, a, reverse=False):
self.reverse = reverse
if reverse:
a = [-v for v in a]
self.a = a
heapify(self.a)
self.rm_list = defaultdict(int)
def heappush(self, item):
if self.reverse: item *= -1
heappush(self.a, item)
def heappop(self):
x = heappop(self.a)
while self.rm_list[x]:
self.rm_list[x] -= 1
x = heappop(self.a)
if self.reverse: x *= -1
return x
def heappushpop(self, item):
if self.reverse:
return -heappushpop(self.a, -item)
else:
return heappushpop(self.a, item)
def rm(self, item):
if self.reverse: item *= -1
self.rm_list[item] += 1
def get_first(self):
while self.rm_list[self.a[0]]:
self.rm_list[self.a[0]] -= 1
heappop(self.a)
if self.reverse: return -self.a[0]
else: return self.a[0]def E():
N, K, Q = map(int, input().split())
A = [0] * (N + 1)
top_k = my_heapq([0] * K) # 通常heap: 先頭が最小
others = my_heapq([0] * (N - K), reverse=True) # 降順heap: 先頭が最大
ans = 0
if N == K:
for _ in range(Q):
x, y = map(int, input().split())
now = A[x]
ans -= now
ans += y
A[x] = y
print(ans)
return
for _ in range(Q):
x, y = map(int, input().split())
now = A[x]
A[x] = y
if now >= top_k.get_first():
top_k.rm(now)
if y >= others.get_first():
# top_kにいて、残る
ans -= now
ans += y
top_k.heappush(y)
else:
# top_kにいて、外れる
ans -= now
new = others.heappop()
ans += new
top_k.heappush(new)
others.heappush(y)
else:
others.rm(now)
if y > top_k.get_first():
# top_kにおらず、入る
old = top_k.heappop()
ans -= old
others.heappush(old)
ans += y
top_k.heappush(y)
else:
# top_kにおらず、入らない
others.heappush(y)
print(ans)
test_all(E)
AtCoder Inc.
