# Length of the Longest Bitonic Subsequence

Given an array, you have to find out the length of the longest bitonic subsequence from the array. A bitonic sequence is a sequence where numbers of that sequence are sorted and they are increasing first then decreasing.

**Note:** A sorted increasing sequence is also a bitonic sequence and similarly sorted decreasing sequence is a bitonic sequence.

Input:
Test Case T
T no. of lines with the value of N and corresponding values.
E.g.
3
5
1 4 2 5 7
8
1 7 3 2 5 4 8 1
17
1 10 9 3 5 4 11 7 4 8 9 6 19 5 7 8 2
Constrains:
1≤ T ≤ 10
1≤ N ≤ 100
1≤ A[i] ≤ 1000
Output:
Print the length of the bitonic subsequence.

**Example**

T = 3
N = 5
1 4 2 5 7
4 (1 2 5 7)
N = 8
1 7 3 2 5 4 8 1
5 (1 3 5 4 1)
N = 17
1 10 9 3 5 4 11 7 4 8 9 6 19 5 7 8 2
9 (1 3 4 7 8 9 6 5 2)

Let,

Nbe the number of elements say,X1, X2, X3, ..., XnNow, possible counting can be:

To find out the

length of the bitonic subsequencewe follow up these steps,Every time we check if any element is lesser then the current element. If this happens then we add up one with the value of that index in the new array and compare with the value of the current element's index in the new array and take the maximum value.

For this sequence:Longest increasing subsequence from front:Longest increasing subsequence from rear:After add up:Therefore, the answer is 5.C++ implementation:Output