Records in Reverse#13116
You are given an array of integers.
Call a position a record position if a_i is strictly greater than every preceding element. The first position is always a record position.
You may perform at most one operation: choose an integer (1\le k\le n) and reverse the first elements of the array.
For example, if a=[4,2,5,1,3] and k=3, the resulting array is [5,2,4,1,3].
Find the maximum possible number of record positions after performing at most one operation.
The first line contains one integer (1\le n\le2\cdot10^5) — the array length.
The second line contains integers a_1,a_2,\ldots,a_n (1\le a_i\le10^9).
Print one integer — the maximum possible number of record positions.
Example 1
Example 2
Example 3
In the first example, reverse the first two elements to obtain [1,2,5,3,4]. Positions are record positions.
In the second example, reverse the whole array to obtain [1,2,3,4]. All four positions are record positions.
In the third example, reverse the first four elements to obtain [2,1,3,3,3]. Positions and are record positions. It is impossible to obtain more than two record positions.
Subtask ( points): n\le100.
Subtask ( points): n\le2000.
Subtask ( points): no additional constraints.