作为 Scholomance 学院的学生，你正在学习一门名为“机器学习”的课程。你目前正在进行课程项目：训练一个二分类器。

二分类器是一种预测实例类别的算法，类别可以是正类（+）或负类（-）。典型的二分类器包含一个评分函数 $S$，它为每个实例给出一个分数，以及一个决定类别的阈值 $\theta$。具体来说，如果一个实例 $x$ 的分数 $S(x) \ge \theta$，则该实例被分类为正类；否则，它被分类为负类。显然，选择不同的阈值可能会产生不同的分类器。

当然，二分类器可能会出现误分类：它可能将正类实例分类为负类（假阴性），或者将负类实例分类为正类（假阳性）。

表 1：预测类别与实际类别。

给定一个数据集和一个分类器，我们可以定义真阳性率 ($TPR$) 和假阳性率 ($FPR$) 如下：

$$TPR = \frac{\#TP}{\#TP + \#FN}, \quad FPR = \frac{\#FP}{\#TN + \#FP}$$

其中 $\#TP$ 是数据集中的真阳性数量；$\#FP, \#TN, \#FN$ 的定义类似。

现在你已经训练了一个评分函数，并希望评估分类器的性能。如果我们改变阈值 $\theta$，分类器可能会表现出不同的 $TPR$ 和 $FPR$。令 $TPR(\theta), FPR(\theta)$ 为阈值为 $\theta$ 时的 $TPR$ 和 $FPR$，定义曲线下面积 (AUC) 为：

$$AUC = \int_{0}^{1} \max_{\theta \in \mathbb{R}} \{TPR(\theta) | FPR(\theta) \le r\} dr$$

其中被积函数称为受试者工作特征 (ROC)，表示在 $FPR \le r$ 的条件下 $TPR$ 的最大可能值。

给定数据集中实例的实际类别和预测分数，你能计算出分类器的 AUC 吗？

例如，考虑第三组测试数据。如果我们设置阈值 $\theta = 30$，则有 3 个真阳性，2 个假阳性，2 个真阴性，以及 1 个假阴性；因此，$TPR(30) = 0.75$ 且 $FPR(30) = 0.5$。此外，随着 $\theta$ 的变化，我们可以绘制 ROC 曲线并据此计算 AUC，如图 3 所示。

图 3：第三组样例数据的 ROC 和 AUC。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 10^6$)，表示数据集中的实例数量。接下来 $n$ 行，每行包含一个字符 $c \in \{+, -\}$ 和一个整数 $s$ ($1 \le s \le 10^9$)，分别表示实例的实际类别和预测分数。

保证至少存在一个正类实例和一个负类实例。

输出格式

输出分类器的 AUC，要求绝对误差不超过 $10^{-9}$。

样例

输入 1

3
+ 2
- 3
- 1

输出 1

0.5

输入 2

6
+ 7
- 2
- 5
+ 4
- 2
+ 6

输出 2

0.888888888888889

输入 3

8
+ 34
+ 33
+ 26
- 34
- 38
+ 39
- 7
- 27

输出 3

0.5625