Valley Avoidance

You are given a parameter $K$. A permutation $P$ of $\{1, 2, \ldots, N\}$ has a *valley* if there exist indices $i_1 \lt i_2 \lt\ldots\lt i_K$ such that $$ \max(P_{i_2}, P_{i_3}, \ldots, P_{i_{K-1}}) < \min(P_{i_1}, P_{i_K}) $$ That is, $P$ has a *valley* if there exists a sequence of $K$ indices such that the leftmost and rightmost elements are both larger than all the "middle" elements. ---