I have a solution that should work in O(N.log^2a[i]_{max})

##
Code

```
import java.io.*;
class Main
{
public static void main(String args[])throws Exception
{
BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb=new StringBuilder();
int n=Integer.parseInt(bu.readLine());
String s[]=bu.readLine().split(" ");
int i,c[]=new int[n],l=1,r=1,mid,ans;
for(i=0;i<n;i++)
{
c[i]=Integer.parseInt(s[i]);
r=Math.max(r,c[i]);
}
s=bu.readLine().split(" ");
int a=Integer.parseInt(s[0]),b=Integer.parseInt(s[1]);
ans=r;
while(l<=r)
{
mid=(l+r)>>1;
if(possible(c,mid,a,b))
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
System.out.println(ans);
}
static boolean possible(int c[],int k,int a,int b)
{
int rem=k,i,n=c.length;
for(i=0;i<n;i++)
{
long v=1l*rem*a+1l*(k-rem)*b;
if(v<c[i]) return false;
int l=0,r=rem,mid,ans=r;
while(l<=r)
{
mid=(l+r)>>1;
v=1l*mid*a+1l*(k-mid)*b;
if(v>=c[i])
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
rem-=ans;
}
return true;
}
}
```

So what I have done here is binary searched the answer, and for any value k, checked if it is possible to make the non positive using x aâ€™s and k-x bâ€™s. Ultimately, what we need is to optimally divide the aâ€™s, so this is what I tried to do.

We need the smallest number of moves for which we can make the entire array non positive

Now suppose we have m moves. This means that \sum_{i=1}^{n}x_i \leq m where x_i is the number of times we are removing a from any index. Now, for any index, we have to find the minimum value of x_i, which can be found by binary search too. If the minimum index is greater than remaining moves(rem), the answer m is not possible, otherwise, we make rem=rem-x_i

Now for this binary search of x_i, suppose we select a number k, which means we are removing a from array element k times. Therefore the total value removed will be a.k+(m-k).b. If this is \geq array element, then k is a valid choice, otherwise its not.

It passes the cases given in the blog(for the last case N=5), but there may be cases where it fails. If anyone can provide such corner cases, or a link where I can submit the code, I would be grateful.