Problem Statement

A sequence is called bitonic if it first strictly increases and then immediately strictly decreases. For example, [100, 200, 100], [100, 200, 300, 50], [100, 200, 50, -100] are bitonic, since they first strictly increases and then strictly decreases whereas [1, 2, 2, 1], [2, 1, 2, 3], and [3, 2, 1] are not. Note that a bitonic sequence must have at least three values. A subsequence of an array is obtained by deleting several elements (possibly zero or all) without changing the order of the remaining elements. For example, [1, 3, 4] are subsequences of [1, 2, 3, 4] whereas [1, 5] and [3, 4] are not. Given an array of arr of size n, find the number of non-empty bitonic subsequences in arr. Since the answer can be very large, compute the value modulo (10^9+7). Example n = 5 arr = [1, 2, 3, 2, 1] The 11 bitonic subsequences are [1, 2, 1], [1, 2, 1], [1, 3, 1], [1, 3, 2], [2, 3, 2], [2, 3, 1], [1, 2, 3, 1], [1, 2, 3, 2], [1, 2, 3, 2, 1], [1, 2, 2, 1], [1, 3, 2, 1]. Return 11. Function Descr