Count Bitonic Subsequences

Problem Statement

Count Bitonic Subsequences A sequence is bitonic when it first strictly increases and then immediately strictly decreases. [100, 200, 100] , [100, 200, 300, 50] and [100, 200, 50, -100] are bitonic. [1, 2, 2, 1] , [2, 1, 2, 3] and [3, 2, 1] are not: the first has two equal neighbours, the second falls before it rises, and the third never rises at all. Precisely, s[0], s[1], ..., s[k-1] is bitonic when there is a position p with 0 < p < k-1 such that s[0] < s[1] < ... < s[p] , and s[p] > s[p+1] > ... > s[k-1] . Both wings must be non-empty, so a bitonic sequence holds at least three values. A sequence that only rises, or only falls, or that repeats a value next to itself, is not bitonic. A subsequence of arr is obtained by deleting zero or more elements without changing the order of the rest. Subsequences are identified by the positions they use, not by the values they spell: two different position sets are two different subsequences even when they read the same.