Task

Compute the Area Under the ROC Curve (AUC) using the trapezoidal rule. Sort samples by descending predicted score. Walk through the sorted list, incrementing true-positive count (tp) for positives and false-positive count (fp) for negatives. At each step record TPR = tp/P and FPR = fp/N. Compute area using the trapezoid rule: AUC = sum over steps of (ΔFPR * (TPRprev + TPRcurr) / 2).

Input

• Line 1: n — number of samples
• Line 2: label_1 ... label_n — binary labels (0 or 1) space-separated
• Line 3: score_1 ... score_n — predicted scores space-separated

Output

Print the AUC as a single float with up to 10 significant digits.

Example

Input:

6
1 0 1 0 1 0
0.9 0.8 0.7 0.6 0.5 0.4

Output:

0.6666666667

Scaffolding

Submit a Python file defining:

def roc_auc(labels: list[int], scores: list[float]) -> float:
    ...

Receives a list of binary labels and a list of predicted scores; returns the AUC as a float.