На кольцевой линии берляндского метро расположено n станций. Известны расстояния между всеми парами соседних станций:
- d1 — расстояние между 1-ой и 2-ой станцией;
- d2 — расстояние между 2-ой и 3-ой станцией;
...
- dn - 1 — расстояние между n - 1-ой и n-ой станцией;
- dn — расстояние между n-ой и 1-ой станцией.
Поезда ходят по кольцевой линии в обоих направлениях. Найдите кратчайшее расстояние между станциями с номерами s и t.
Выходные данные
Выведите одно число — длину кратчайшего пути между станциями с номерами s и t.
Примечание
В первом примере длина пути 1 → 2 → 3 равна 5, длина пути 1 → 4 → 3 равна 13.
Во втором примере длина пути 4 → 1 равна 100, длина пути 4 → 3 → 2 → 1 равна 15.
В третьем примере длина пути 3 → 1 равна 1, длина пути 3 → 2 → 1 равна 2.
В четвертом примере номера станций совпадают, поэтому кратчайшее расстояние равно 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 3 4 9
1 3
|
5
|
|
2
|
4
5 8 2 100
4 1
|
15
|
|
3
|
3
1 1 1
3 1
|
1
|
|
4
|
3
31 41 59
1 1
|
0
|