Вы наверняка слышали легенду о Короле Артуре и Рыцарях Круглого Стола. Практически все версии этой истории указывают на то, что круглость Круглого Стола тесно связана с верой Артура в равенство среди рыцарей. Это ложь! На самом деле выбор Артура касательно формы стола вызван его детской травмой.

В реальности Артур был принужден убирать и мыть квадратные столы с юного возраста после того как на них играли в бирюльки. После соревнований по этой игре обычно на столе остается множество палочек, не касающихся друг друга. В духе соревнования, организаторы установили свод строгих правил для уборщиков. Точнее, палочки со стола должны быть убраны одна за другой путем их сдвига к ближайшему к уборщику краю стола. Они не должны вращаться и касаться других палочек в процессе перемещения.

В этой задаче представим стол на координатной плоскости как квадрат с противоположными вершинами в точках (0, 0) и (10000, 10000), где палочкам соответствуют прямые отрезки, лежащие внутри квадрата. Предположим, что Артур сидит у края стола, прилежащего к оси X. Тогда уборка палочек со стола сводится к передвижению их к оси X, покуда они не упадут со стола. Ваша задача - определить порядок уборки палочек со стола, который соответствует условиям из предыдущего абзаца.

Хранители в опасности, и Доктор Манхэттен со своим другом Дэниелом Драйбергом должны срочно их предупредить. Всего в команде хранителей n человек, i -й из которых находится в точке плоскости с координатами ( x _i , y _i ) .

Как всем известно, доктор Манхэттен вычисляет расстояние между двумя хранителями i и j по формуле | x _i - x _j | + | y _i - y _j | . Дэниел, как обычный человек, считает, что расстояние равно .

Сейчас успех операции зависит от того, сколько существует пар ( i , j ) ( 1 ≤ i < j ≤ n ), таких что расстояние между хранителем i и хранителем j , вычисленное Доктором Манхэттеном, равняется расстоянию между ними, вычисленному Дэниелом. Вычислить эту величину попросили именно вас.

Организаторы CEOI 2011 собираются устроить вечеринку с кучей воздушных шариков. Всего будет \(n\) шариков (они все имеют форму идеального шара), и они будут лежать на одной линии на полу.

Шарики ещё не надуты, и каждый из них изначально имеет нулевой радиус. Ещё, \(i\)-й шар прикреплён к полу в позиции \(x_i\). Они будут надуваться последовательно, слева направо. Когда какой-то шарик надувается, его радиус непрерывно увеличивается, пока не достигнет верхней границы своего размера, \(r_i\), либо же не каснётся одного из уже надутых. Картинка 1: Шары из примера, после надувания.

Организваторы хотели бы оценить, сколько воздуха понадобится для надувания. Найдите, пожалуйста, итоговый радиус каждого шара.

Теперь вас назначили управляющим одной телекоммуникационной компании. Вы отвечаете за обеспечение маленького городка контентом. Каждый дом задается его координатами на плоскости. Известно, что никакие три дома не лежат на одной прямой, а никакие четыре на одной окружности. Вы решили поставить одну антенну так, чтобы сигнал от нее был доступен домам в определенным радиусе, т.е. область, в которой доступен контент является кругом. Вы еще не очень разобрались в политике вашей компании, поэтому решили сделать не слишком сложный выбор данной области: вы просто выбираете 3 случайных дома и строите круг так, чтобы эти три дома были на его границе (вы ходили на геометрию в 7 классе и вам известно, что так всегда можно сделать). Теперь вам интересно, сколько в среднем домов будут иметь доступ к контенту. Выведите ответ с точностью до 4 знаков после запятой.