У RSJ есть последовательность \(a\) из \(n\) целых чисел \(a_1,a_2, \ldots, a_n\) и целое число \(s\). Для каждого \(a_2,a_3, \ldots, a_{n-1}\) он выбрал пару неотрицательных целых чисел \(x_i\) и \(y_i\) такую, что \(x_i+y_i=a_i\) и \((x_i-s) \cdot (y_i-s) \geq 0\).
Теперь он заинтересовался значением \(\)F = a_1 \cdot x_2+y_2 \cdot x_3+y_3 \cdot x_4 + \ldots + y_{n - 2} \cdot x_{n-1}+y_{n-1} \cdot a_n.\(\)
Помогите ему найти минимально возможное значение \(F\) при оптимальном выборе \(x_i\) и \(y_i\). Можно показать, что всегда существует хотя бы один корректный способ выбрать эти числа.
Выходные данные
Для каждого набора входных данных выведите минимальное значение \(F\).
Примечание
В первом наборе входных данных \(2\cdot 0+0\cdot 1+0\cdot 3+0\cdot 4 = 0\).
Во втором наборе входных данных \(5\cdot 1+2\cdot 2+2\cdot 2+1\cdot 5 = 18\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
5 0
2 0 1 3 4
5 1
5 3 4 3 5
7 2
7 6 5 4 3 2 1
5 1
1 2 3 4 5
5 2
1 2 3 4 5
4 0
0 1 1 1
5 5
4 3 5 6 4
4 1
0 2 1 0
3 99999
200000 200000 200000
6 8139
7976 129785 12984 78561 173685 15480
|
0
18
32
11
14
0
16
0
40000000000
2700826806
|