A concave subsequence is a subsequence where the first and last elements are greater than all other elements in between. For example, [100, 0, 25, 11, 200] is concave, while [100, 0, 110, 200] 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 the 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.

Function Description

Complete the function maxLength in the editor.

maxLength has the following parameter:

1. int arr[n] : the array

Returns

int: the length of the longest subsequence having the required property

Example 1 :

Input: arr = [4, 2, 6, 5, 3, 1]
Output: 3
Explanation: There are three longest subsequences: [4, 2, 6], [4, 2, 5], and [4, 2, 3]. Return 3, the length of these subsequences.

Example 2 :

Input: arr = [3, 1, 5, 2, 4]
Output: 4
Explanation: The longest subsequence satisfying the requirement is [3, 1, 2, 4].

Example 3 :

Input: arr = [1, 2, 3, 4, 5]
Output: 2
Explanation: My subsequence of 2 elements satisfies the requirements.

Constraints: