Make the Sum Divisible

Write shortest_cut(nums, p) that finds the shortest subarray (a stretch of neighbouring items, possibly empty) you can remove from nums so that the sum of the remaining items is divisible by p, and returns its length.

You may not remove the whole list. Return -1 if it cannot be done.

Examples

shortest_cut([3, 1, 4, 2], 6)  # returns 1
shortest_cut([6, 3, 5, 2], 9)  # returns 2
shortest_cut([1, 2, 3], 3)     # returns 0
shortest_cut([1, 2, 3], 7)     # returns -1

In the first example the total is 10, and removing the 4 leaves 6. In the last example the only way to reach a multiple of 7 is to remove everything, which is not allowed.

Constraints

• 1 <= len(nums) <= 100,000
• 1 <= nums[i] <= 10**9
• 1 <= p <= 10**9