A concave subsequence is a subsequence where the first and last elements are greater than all other elements in between. For example,

$[$

$1$

$0$

$0$

$,$

$0$

$,$

$2$

$5$

$,$

$1$

$1$

$,$

$2$

$0$

$0$

$]$

$$is concave, while

$[$

$1$

$0$

$0$

$,$

$0$

$,$

$1$

$1$

$0$

$,$

$2$

$0$

$0$

$]$

$$is not since the third element is greater than the first element.

Given an array that contains a permutation of n integers, arr

$[$

n

$]$

$,$

$$determine length of the longest concave subsequence.

A permutation is a sequence of integers from

$1$

$$to n that contains each number exactly once. For example

$[$

$1$

$,$

$3$

$,$

$2$

$]$

$$is a permutation while

$[$

$1$

$,$

$2$

$,$

$1$

$]$

$$and

$[$

$1$

$,$

$2$

$,$

$4$

$]$

$$are not.

A subsequence is derived from a sequence by deleting zero or more elements without changing the order of the remaining elements. For example

$[$

$3$

$,$

$4$

$]$

$$is a subsequence of

$[$

$5$

$,$

$3$

$,$

$2$

$,$

$4$

$]$

$,$

$$but

$[$

$4$

$,$

$3$

$]$

$$is not.