D - 中央値チェック 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は、整数の多重集合（同じ値を複数含むことができる集合）に対して要素の追加と削除を繰り返し、ある条件を満たす削除が何回発生するかを数えたいと思っています。

最初、多重集合は空です。以下の 2 種類のクエリが Q 個、順番に与えられます。i 番目のクエリで指定される値を X_i とします。

  • + X_i：多重集合に値 X_i を 1 つ追加する。
  • - X_i：多重集合から値 X_i を 1 つ削除する。この時点で多重集合に値 X_i が少なくとも 1 つ存在することは保証される。

削除クエリにおいて、削除する値 X_i が 削除する直前の多重集合の中央値と一致する 場合、この削除を「中央値ヒット」と呼びます。

ここで、要素数 n（n \geq 1）の多重集合の中央値を次のように定めます。すべての要素を昇順に並べたとき、\lceil n/2 \rceil 番目（1-indexed）の値を中央値とします。すなわち、要素数が奇数のときは真ん中の値、偶数のときは真ん中 2 つのうち小さい方の値です。

削除クエリの時点では多重集合に少なくとも 1 つの要素が存在するため、中央値は常に定義されます。

すべてのクエリを順に処理したとき、「中央値ヒット」が発生した回数を求めてください。

制約

  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq X_i \leq 10^9
  • - X_i のクエリが与えられる時点で、多重集合に値 X_i が少なくとも 1 つ存在する。
  • 入力で与えられる数値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

Q
Query_1
Query_2
\vdots
Query_Q

各 Query_i（1 \leq i \leq Q）は + X_i または - X_i の形式であり、クエリの種類を表す文字（+ または -）と正の整数 X_i が空白区切りで与えられる。

出力

「中央値ヒット」が発生した回数を整数として一行で出力せよ。

入力例 1

6
+ 1
+ 3
+ 2
- 2
- 1
- 3

出力例 1

3

入力例 2

8
+ 10
+ 20
- 20
+ 15
+ 25
- 25
- 10
- 15

出力例 2

2

入力例 3

15
+ 5
+ 1
+ 5
+ 3
+ 3
- 3
+ 4
- 5
+ 2
- 3
+ 5
- 4
- 5
- 1
- 2

出力例 3

4

入力例 4

25
+ 1000000000
+ 7
+ 7
+ 500
+ 8
- 7
+ 6
- 8
+ 9
+ 10
- 7
+ 9
- 9
+ 1
- 6
+ 2
+ 3
- 9
+ 4
- 4
- 1000000000
- 3
- 1
- 10
- 2

出力例 4

7

入力例 5

1
+ 1000000000

出力例 5

0

Score : 400 pts

Problem Statement

Takahashi wants to repeatedly add and remove elements from a multiset of integers (a set that can contain multiple copies of the same value), and count how many removals satisfy a certain condition.

Initially, the multiset is empty. You are given Q queries in order, of the following 2 types. Let X_i denote the value specified by the i-th query.

  • + X_i: Add one copy of the value X_i to the multiset.
  • - X_i: Remove one copy of the value X_i from the multiset. It is guaranteed that at least one copy of the value X_i exists in the multiset at this point.

For a removal query, if the value X_i being removed matches the median of the multiset immediately before the removal, this removal is called a "median hit".

Here, the median of a multiset with n elements (n \geq 1) is defined as follows: when all elements are sorted in ascending order, the \lceil n/2 \rceil-th value (1-indexed) is the median. In other words, when the number of elements is odd, it is the middle value; when even, it is the smaller of the two middle values.

Since the multiset contains at least one element at the time of a removal query, the median is always well-defined.

Process all queries in order and determine the number of times a "median hit" occurs.

Constraints

  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq X_i \leq 10^9
  • At the time a - X_i query is given, at least one copy of the value X_i exists in the multiset.
  • All numerical values given in the input are integers.

Input

Input is given from standard input in the following format:

Q
Query_1
Query_2
\vdots
Query_Q

Each Query_i (1 \leq i \leq Q) is in the format + X_i or - X_i, where the character representing the query type (+ or -) and the positive integer X_i are given separated by a space.

Output

Output the number of times a "median hit" occurs, as a single integer on one line.

Sample Input 1

6
+ 1
+ 3
+ 2
- 2
- 1
- 3

Sample Output 1

3

Sample Input 2

8
+ 10
+ 20
- 20
+ 15
+ 25
- 25
- 10
- 15

Sample Output 2

2

Sample Input 3

15
+ 5
+ 1
+ 5
+ 3
+ 3
- 3
+ 4
- 5
+ 2
- 3
+ 5
- 4
- 5
- 1
- 2

Sample Output 3

4

Sample Input 4

25
+ 1000000000
+ 7
+ 7
+ 500
+ 8
- 7
+ 6
- 8
+ 9
+ 10
- 7
+ 9
- 9
+ 1
- 6
+ 2
+ 3
- 9
+ 4
- 4
- 1000000000
- 3
- 1
- 10
- 2

Sample Output 4

7

Sample Input 5

1
+ 1000000000

Sample Output 5

0