Given an array nums of integers, a move&nbsp;consists of choosing any element and decreasing it by 1.

An array A is a&nbsp;zigzag array&nbsp;if either:


	Every even-indexed element is greater than adjacent elements, ie.&nbsp;A[0] &gt; A[1] &lt; A[2] &gt; A[3] &lt; A[4] &gt; ...
	OR, every odd-indexed element is greater than adjacent elements, ie.&nbsp;A[0] &lt; A[1] &gt; A[2] &lt; A[3] &gt; A[4] &lt; ...


Return the minimum number of moves to transform the given array nums into a zigzag array.

&nbsp;
Example 1:

Input: nums = [1,2,3]
Output: 2
Explanation: We can decrease 2 to 0 or 3 to 1.


Example 2:

Input: nums = [9,6,1,6,2]
Output: 4


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 1000
	1 &lt;= nums[i] &lt;= 1000


class Solution:
    def solve(self,arr,n,x):
        idx = 1
        ans = 0
        while idx < n:
            if idx == 0: idx += 1
            if idx % 2 == x:
                if arr[idx-1] >= arr[idx]:
                    ans += arr[idx-1] - arr[idx] + 1
                    arr[idx-1] = arr[idx] - 1
                    idx = idx-1
                else:
                    idx = idx+1
            else:
                if arr[idx-1] <= arr[idx]:
                    ans += arr[idx] - arr[idx - 1] + 1
                    arr[idx] = arr[idx-1] - 1
                idx += 1               
        return ans
    
    def movesToMakeZigzag(self, nums: List[int]) -> int:
        ans1 = self.solve([x for x in nums],len(nums),0)
        ans2 = self.solve([x for x in nums],len(nums),1)
        return min(ans1,ans2)
class Solution {
    /*
        firstly, check elements in odd indices are greater than its neighbours.
        if not, decrease its neigbours and update the cost.
        
        do same thing for even indices, because there can be two combinations as indicated in question.
    */
    
    private int calculateCost(int[] nums, int start){
        int res = 0;
        int n = nums.length;
        int[] arr = Arrays.copyOf(nums, nums.length); // nums array will be modified, so copy it.
        
        for(int i=start;i<n;i+=2){
            int prev = (i==0) ? Integer.MIN_VALUE : arr[i-1]; 
            int cur = arr[i];
            int next = (i == n-1) ? Integer.MIN_VALUE : arr[i+1];
            
            if(prev < cur && next < cur)
                continue;
        
            if(prev >= cur){
                res += prev-cur +1;
                arr[i-1] = cur-1;
            } 
            
            if(next >= cur){
                res += next-cur +1;
                arr[i+1] = cur-1;
            }
        }
        return res;
    }
        
    public int movesToMakeZigzag(int[] nums) {
        return Math.min(calculateCost(nums, 0), calculateCost(nums,1));
    }
}
class Solution {
public:
    int movesToMakeZigzag(vector<int>& nums) {
        int oddSum = 0, evenSum = 0;
        int n = nums.size();
        for(int i=0; i<n; i++){
            if(i%2 == 0){
                int left = i==0?INT_MAX:nums[i-1];
                int right = i==n-1?INT_MAX:nums[i+1];
                evenSum += max(nums[i]-min(left,right)+1,0);
            }else{
                int left = i==0?INT_MAX:nums[i-1];
                int right = i==n-1?INT_MAX:nums[i+1];
                oddSum += max(nums[i]-min(left,right)+1,0);
            }
        }
        return min(evenSum,oddSum);
    }
};
var movesToMakeZigzag = function(nums) {
    const n = nums.length;

    let lastEvenRight = Number.MIN_SAFE_INTEGER;
    let evenMoves = 0;

    let lastOddRight = nums[0];
    let oddMoves = 0;

    for (let i = 0; i < n; i++) {
        const currNum = nums[i];
        const nextNum = i < n - 1 ? nums[i + 1] : Number.MIN_SAFE_INTEGER;

        if (i % 2 === 0) {
            if (lastEvenRight >= currNum) evenMoves += lastEvenRight - currNum + 1;

            if (currNum <= nextNum) {
                evenMoves += nextNum - currNum + 1;
            }

            lastEvenRight = Math.min(currNum - 1, nextNum);
        }
        else {
            if (lastOddRight >= currNum) oddMoves += lastOddRight - currNum + 1;

            if (currNum <= nextNum) {
                oddMoves += nextNum - currNum + 1;
            }

            lastOddRight = Math.min(currNum - 1, nextNum);
        }
    }

    return Math.min(oddMoves, evenMoves);
};
Decrease Elements To Make Array Zigzag