Firstly use two-pointer to make the problem become something like to check whether a subarray is good.
A key observation is that if there exist i → a[i]>a[i+1] then you must erase one of them. So if there exist at least 2 i’s satisfies the condition, call them x&y, there will be 4 options: erase x&y; x+1&y; x&y+1; x+1&y+1. If you appoint 2 erase indexes a and b, it’s easy to find that |a-b|%d=0. Thus there are only D(n) choices for the d. If the d is confirmed, it’s easy to check whether the array is good or not.
Then for the next part: only one i that a[i]>a[i+1]. It has some cases very annoying like 2 2 1 1. I make up one method to check, but I can’t prove it’s sufficient. It’s like: for the contiguous four elements: a[x+1]~a[x+4], you can only erase: {a[x+1]&a[x+3]; a[x+1]&a[x+4]; a[x+2]&a[x+4]}. Thus there must be one of the three conditions below holds: a[x+2]>=a[x+4]; a[x+2]>=a[x+3]; a[x+1]>=a[x+3]. I just check for every i if it feats this condition, and my solution passed.
The total complexity is O(n^2*d(n)). btw I’ll be grateful if anyone can prove my solution of the second part.