Alex on his walk to Forest of leaf discovers N sticks lying in front of him. Each stick has two values represented by two arrays arr and price of size N where in array arr, arr[i] (0<=i<=N−1) denotes length of i′th stick and array price, price[i] (0<=i<=N−1) denotes price to increment length of i′th stick by 1 unit.
Alex calls an array Broken Adjacency when none of the adjacent sticks has equal length. A stick i is adjacent to stick i−1 (if any) and stick i+1 (if any). He wants to find the minimum cost to achieve Broken Adjacency. To do so, in 1 move he can increment the length of any i′th stick by 1 unit at the price of price[i].
Can you help him find the minimum cost to achieve his goal?
Input Format:
Output Format:
Print the minimum cost to make given sticks to Broken Adjacent sticks.
Constraints:
1<=T<=10
1<=N<=105
1<=arr[i]<=109
1<=price[i]<=109
For test case 1,
Alex will increment 2 (i = 1) by 2 units and the final array will look like [ 2, 4, 3 ]. The total cost of this operation will be 2. Alex cannot achieve a lower cost than 2.
For test case 2,
Alex needs to increment the length of stick 3 (i = 1) by 2 units. The final array will look like [ 3, 5, 4 ] , the total cost equals 2.
For test case 3,
The sticks are already Broken Adjacent.