Task

Compute the ROC AUC via the trapezoidal rule and derive the Gini coefficient from it. Sort samples by descending predicted score. Walk through the sorted list incrementing tp (true positives) and fp (false positives) counters. At each step record TPR = tp/P and FPR = fp/N where P and N are total positives and negatives. Compute AUC = sum over consecutive steps of (ΔFPR * (TPRprev + TPRcurr) / 2). The Gini coefficient is Gini = 2 * AUC - 1.

Input

• Line 1: n — number of samples
• Line 2: y_1 ... y_n — true binary labels (0 or 1) space-separated
• Line 3: s_1 ... s_n — predicted scores space-separated

Output

• Line 1: AUC as a float with up to 10 significant digits
• Line 2: Gini coefficient as a float with up to 10 significant digits

Example

Input:

4
0 0 1 1
0.1 0.4 0.35 0.8

Output:

0.75
0.5

Scaffolding

Submit a Python file defining:

def roc_auc_gini(y_true: list[int], scores: list[float]) -> tuple[float, float]:
    ...

Receives a list of true binary labels and predicted scores; returns a tuple (auc, gini_coefficient).