В столице Берляндии построили метро. Изначально была только одна центральная станция номер 1, а затем сеть разрасталась: добавлялись новые станции и перегоны. Время проезда по любому перегону составляет ровно 1 минуту, и движение возможно в обе стороны. Станции пронумерованы от 1 до $$$n$$$, где станция 1 — центральная.

Позднее из-за экономического кризиса пришлось закрыть множество перегонов, оставив ровно $$$n-1$$$ перегон так, чтобы от центра по-прежнему можно было добраться до любой станции. Сейчас экономика Берляндии снова на подъёме, и мэр решил построить ровно один новый перегон между какими-то двумя станциями, чтобы улучшить транспортную доступность.

Новый перегон должен быть построен так, чтобы суммарное время поездки от центра до всех станций стало минимальным. Формально, нужно минимизировать сумму $$$\text{dist}(1, i)$$$ по всем $$$i$$$ от $$$1$$$ до $$$n$$$, где $$$\text{dist}(a, b)$$$ — минимальное время в минутах, необходимое, чтобы добраться от станции $$$a$$$ до станции $$$b$$$ по существующим и новому перегону.

Помогите мэру Берляндии найти это минимальное возможное значение суммы.

В задаче используется оценка по группам. Баллы за группу начисляются только при прохождении всех тестов группы. Группа тестируется только если все необходимые предыдущие группы были пройдены. Обозначим $$$p_i$$$ ближайшую станцию на пути до центра от станции $$$i$$$.