У вас есть забор, состоящий из \(n\) вертикальных досок. Ширина каждой доски равна \(1\). Высота \(i\)-й доски равна \(a_i\). Вы считаете забор великим, если все соседние доски имеют разную высоту. Формально, забор великий, если для любого индекса от \(2\) до \(n\), выполняется условие \(a_{i-1} \neq a_i\).
К сожалению, ваш забор может быть не великим. Но вы можете это исправить! Вы можете увеличить длину \(i\)-й доски на \(1\), но за это вам придется заплатить \(b_i\) рублей. Длину каждой доски можно увеличивать любое количество раз (в том числе, можно не увеличивать её длину совсем).
Посчитайте минимальное количество рублей, которое вам нужно потратить, для того чтобы сделать забор великим снова!
Вам нужно ответить на \(q\) независимых запросов.
Выходные данные
На каждый запрос выведите число в отдельной строке — минимальное количество рублей, которое вам нужно потратить, для того чтобы сделать забор великим.
Примечание
В первом запросе вам нужно увеличить длину второй доски на \(2\). Тогда всего вы потратите \(2 \cdot b_2 = 2\) рублей.
Во втором запросе вам нужно увеличить длину первой доски на \(1\) и длину третьей доски на \(1\). Таким образом, вы потратите \(1 \cdot b_1 + 1 \cdot b_3 = 9\) рублей.
В третьем тестовом примере забор великий изначально, поэтому вам не нужно тратить деньги.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
2 4
2 1
3 5
3
2 3
2 10
2 6
4
1 7
3 3
2 6
1000000000 2
|
2
9
0
|