题目描述

在一片战乱的大陆上，村庄是平民赖以生存的庇护所。然而，频繁的冲突让许多村庄面临生死存亡的危机。为了保护这些村庄并高效分配资源，一位战略指挥官阿兔需要设计一套方案来管理村庄的动态分布。

作为一名精通策略的指挥官，你受命协助阿兔完成这项艰巨任务。具体需求如下：

• $add$ $val$ ：新建村庄，当难民聚集形成新的村庄时，阿兔需要迅速记录村庄的位置。
• $remove$ $val$ ：轰炸村庄，敌军的袭击可能摧毁某些村庄，阿兔需要及时更新村庄分布，删除被摧毁的村庄。若同个位置有多个村庄，则仅摧毁一个村庄，若没有村庄，则不会摧毁村庄。
• $query$ ：空投物资，为了让物资运送更加高效，阿兔需要计算将物资空投到哪个位置，使得所有村庄到该位置的总距离最小。

阿兔需要你设计一个高效的系统，能够快速响应每次村庄的增减，并实时计算空投物资的最优方案。战局瞬息万变，任何拖延都可能导致无法挽回的损失。

输入格式

第一行包含一个正整数 $n \ (1\leq n \leq 2*10^{5})$，表示操作的总次数。

接下来 $n$ 行，每行表示一次战况：

• 若战况为空投物资，则只包含一个字符串 $opt$
• 若战况为新建、轰炸村庄，则包含一个字符串和一个整数 $opt$ $val$

其中 $val$ 表示要新建、轰炸的村庄的位置。 $(opt \in \{“add”,“remove”,“query” \}, 1\leq val \leq10^{9})$

输出格式

若为空投物资，则输出一行包含一个整数，表示所有村庄到空投物资的总距离最小值。

11
add 1
add 2
add 3
query
remove 2
add 5
query
add 8
add 9
remove 1
query

2
4
9