Given an integer array nums and an integer p, you may remove exactly one contiguous subarray from nums (possibly removing nothing). After the removal, the remaining elements keep their original order.

Return the minimum possible length of a subarray that can be removed so that the sum of the remaining elements is divisible by p. If it is impossible to achieve divisibility without removing the entire array, return $-1$.

Note: Removing the entire array is not allowed.

Constraints:

• $1 \leq$ nums.length $\leq 10^5$

• $1 \leq$ nums[i] $\leq 10^9$

• $1 \leq$ p $\leq 10^9$

Input: nums = [2,7,1,8]-List[int], p = 5-int
Output: 1-int
Explanation: The total sum is 18, and 18 % 5 = 3, so we need to remove a subarray whose sum is congruent to 3 (mod 5) to make the remaining sum divisible by 5. Removing [8] (8 % 5 = 3) works, and its length 1 is minimal.

Input: nums = [5,10,15]-List[int], p = 5-int
Output: 0-int
Explanation: The total sum is 30, and 30 % 5 = 0, so the array sum is already divisible by p. Removing nothing (length 0) is allowed and optimal.

Input: nums = [4,4,4]-List[int], p = 7-int
Output: -1-int
Explanation: The total sum is 12, and 12 % 7 = 5, so we need to remove a subarray with sum ≡ 5 (mod 7). The possible subarray sums modulo 7 are 4, 1 (for 4+4=8), and 5 (for 4+4+4=12), and the only way to get 5 is removing the entire array (length 3), which is not allowed, so the answer is -1.

Input: nums = [1,1,1,1]-List[int], p = 10-int
Output: -1-int
Explanation: The total sum is 4, and 4 % 10 = 4, so we need to remove a subarray with sum ≡ 4 (mod 10). The only subarray with sum 4 is the entire array, which cannot be removed, so it’s impossible and we return -1.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.