Freaks City

Consider a sequence $A = (a_1, a_2, \dots, a_n)$. We want to partition $A$ into contiguous subsequences, and then arrange these subsequences to form a new sequence $f_1, f_2, \dots, f_k$. Each contiguous subsequence $f_1, \dots, f_p$ must satisfy either $f_1 \le f_2 \le \dots \le f_p$ or $f_1 \ge f_2 \ge \dots \ge f_p$. The cost associated with ...