Task

Compute the Average Precision (AP) score, which summarises the Precision-Recall curve as a weighted mean of precisions at each recall threshold. Sort samples by descending score. For each position k where the label is positive, record precision@k = (true positives so far) / k. AP = (1 / P) * sum of precision@k over all positive-label positions, where P is the total number of positives.

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 Average Precision 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.7555555556

Scaffolding

Submit a Python file defining:

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

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