\(n\) людей живут на координатной прямой, \(i\)-й человек живет в точке \(x_i\) (\(1 \le i \le n\)). Они хотят выбрать точку \(x_0\) для встречи. \(i\)-й человек потратит \(|x_i - x_0|\) минут, чтобы добраться до места встречи. Также \(i\)-му человеку требуется \(t_i\) минут чтобы одеться, поэтому суммарно ему нужно \(t_i + |x_i - x_0|\) минут чтобы добраться до места встречи.
Здесь \(|y|\) обозначает модуль числа \(y\).
Эти люди просят вас выбрать позицию \(x_0\), которая минимизирует время, через которое все \(n\) людей доберутся до места встречи.
Выходные данные
Для каждого набора входных данных выведите единственное вещественное число — оптимальная позиция \(x_0\). Можно показать, что существует единственная оптимальная позиция \(x_0\).
Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит \(10^{−6}\). Формально, пусть ваш ответ равен \(a\), а ответ жюри равен \(b\). Ваш ответ будет зачтен, если \(\frac{|a−b|}{max(1,|b|)} \le 10^{−6}\).
Примечание
- В \(1\)-м наборе входных данных есть только один человек, поэтому целесообразно выбрать место встречи в его позиции. Тогда он доберется до него за \(3\) минуты, которые нужны ему, чтобы одеться.
- Во \(2\)-м наборе входных данных есть \(2\) человека, которым не нужно время, чтобы одеться. Чтобы добраться до позиции \(2\), каждому из них потребуется по одной минуте.
- В \(5\)-м наборе входных данных \(1\)-му человеку нужно \(4\) минуты, чтобы добраться до позиции \(1\) (\(4\) минуты, чтобы одеться, и \(0\) минут на сам путь); \(2\)-му человеку нужно \(2\) минуты, чтобы добраться до позиции \(1\) (\(1\) минута, чтобы одеться, и \(1\) минута на сам путь); \(3\)-му человеку нужно \(4\) минуты, чтобы добраться до позиции \(1\) (\(2\) минуты, чтобы одеться, и \(2\) минуты на сам путь).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1
0
3
2
3 1
0 0
2
1 4
0 0
3
1 2 3
0 0 0
3
1 2 3
4 1 2
3
3 3 3
5 3 3
6
5 4 7 2 10 4
3 2 5 1 4 6
|
0
2
2.5
2
1
3
6
|