Notice that an ideal array is non-decreasing.

Consider an alternative problem: where an ideal array must also be strictly increasing. Can you use DP to solve it?

Will combinatorics help to get an answer from the alternative problem to the actual problem?