Problem Statement

Given an array arr of n integers, modify the array to make it positive using the following operation: In a single operation, select an index i ( 0 ≤ i < n ) and a value x with -10 8 ≤ x ≤ 10 8 , and change arr[i] to x . An array is considered positive when the sum of every subarray of length greater than 1 is non-negative. Formally, after the operations the following condition should hold for all values of l and r where 0 ≤ l < r < n : arr[l] + arr[l+1] + ... + arr[r] ≥ 0 Determine the minimum number of operations required to make the array positive. Input Format The first line contains an integer n , the size of the array. Each of the next n lines contains one integer, arr[i] . Output Format Print a single integer — the minimum number of operations required. Constraints 1 ≤ n ≤ 10 5 -10 9 ≤ arr[i] ≤ 10 9 , where 0 ≤ i < n A replacement value x must satisfy -10 8 ≤ x ≤ 10 8 Sample Testcase 1 Input 5 2 5 -8 -1 2 Output 1 Explanation: