Task

Given a list of 1D feature values and binary labels, find the threshold that maximises Gini impurity gain. For each candidate threshold t (taken from the unique feature values), split samples into left (feature <= t) and right (feature > t), then compute gain = Gini(parent) - (|left|/n)Gini(left) - (|right|/n)Gini(right), where Gini(S) = 1 - p² - (1-p)² and p is the fraction of positive labels in S. Return the threshold and the best gain achieved.

Input

• Line 1: n — number of samples
• Lines 2 to n+1: feature label — one float feature value and one integer label (0 or 1) per line

Output

Print threshold gain on a single line, both as floats with up to 10 significant digits.

Example

Input:

6
1.0 0
2.0 0
3.0 1
4.0 1
5.0 1
6.0 0

Output:

2 0.25

Scaffolding

Submit a Python file defining:

def best_split(features: list[float], labels: list[int]) -> tuple[float, float]:
    ...

Receives a list of 1D feature values and a list of binary labels, and returns a tuple (threshold, gain) where threshold is the best split point and gain is the corresponding Gini impurity gain.