問題
無限に続く数直線があります。
YDKはこの数直線上にオーラを発生させます。
具体的には、$x$座標 $l$ から $r$ までの範囲 ($r$ も含む) に、正もしくは負のオーラを発生させることを $N$ 回繰り返します。
各地点にはポテンシャルというものがあり、最初は全て0となっています。
正のオーラを発生させた場合、その区間のポテンシャルは+1され、負のオーラを発生させた場合は-1されます。
YDKは気まぐれなので、正のオーラを発生させることもあれば負のオーラを発生させることもあります。
$N$ 個のオーラを発生させたあとの、ポテンシャルが最も高い座標のポテンシャルを求めてください。
入力
N l1 r1 type1 : lN rN typeN
1行目に、オーラを発生させる回数 $N$ が与えられる。
$N$ 行にわたって、オーラを発生させる範囲 $l$, $r$ と極性 $type$ が入力される。
これは、$type$ が '+' のときは正のオーラで、'-' のときは負のオーラであることを意味する。
出力
$N$ 個のオーラを発生させたあとの、ポテンシャルが最も高い座標のポテンシャルを1行に出力する。
制約
- $1 \le N \le 10^5$
- $-10^5 \le l , r \le 10^5$
- $l \le r$
- $type$ は '+' か '-' のどちらか一方
- $N$, $l$, $r$ は全て整数
入出力例
Sample Input1
3 2 4 + 3 5 - 0 8 +
Sample Output1
2
以下のような動きとなる。
- 区間 [2, 4] のポテンシャルが$+1$される
- 区間 [3, 5] のポテンシャルが$-1$される
- 区間 [0, 8] のポテンシャルが$+1$される
座標 $2$ のポテンシャルが2となり、これが最大である。
Sample Input2
1 -100000 100000 -
Sample Output2
0
区間 [-100,000, 100,000] のポテンシャルが-1されるが、それ以外の空間はデフォルトの0なので、0が最大となる。