Minimum Changes for Target Subarray Sum

You are given an array of integers nums and an integer target. You are allowed to change the value of any element in nums to any integer. Your task is to determine the minimum number of elements you need to change so that there exists a contiguous subarray (i.e. a subarray) whose sum is exactly equal to target.

Observation: It always suffices to change at most one element. In particular, if the array already contains a subarray whose sum equals target, the answer is 0; otherwise, the answer is 1, because you can always change one element (for example, by adjusting one element in the entire array) to make the sum of the whole array equal to target or create some desired subarray.

Note: A subarray is defined as a contiguous segment of the array.

Examples:

• For nums = [1, 2, 3, 4] and target = 6, since 1+2+3 = 6 is a subarray, the answer is 0.
• For nums = [1, 2, 3] and target = 7, no subarray sums to 7, so the answer is 1.
• For nums = [5, 1, 1, 3] and target = 9, the answer is 1 as one change can create a valid subarray summing to 9.

inputFormat

The first line contains an integer n representing the number of elements in the array.

The second line contains n space-separated integers representing the elements of the array nums.

The third line contains an integer target, the target subarray sum.

outputFormat

Output a single integer: the minimum number of changes needed so that there exists a contiguous subarray whose sum is exactly equal to target.

## sample

4
1 2 3 4
6

0