Let's use pref_m[i][x], pref_le[i][x], suff_m[i][x], suff_le[i][x] where:
pref_m[i][x] - on [0;i) elements > x are in decreasing order;
pref_le[i][x] - on [0;i) elements <= x are in increasing order;
suff_m[i][x] - on [i;n) elements > x are in increasing order;
suff_le[i][x] - on [i;n) elements <= x are in decreasing order.

There is inc-dec-solution if and only if there exists some pos and val such that pref_m[pos][val], pref_le[pos][val], suff_m[pos][val] and suff_le[pos][val] are all true.

In order not to get ML you need to remove either positions or values from these arrays. It's your call to chose