You have an array A of n distinct integers. You used the method for generating forests but you didn't like the number of trees generated. You want to remove at most one element to maximize the number of trees in the generated forest. What is the maximum number of trees you can achieve?
Solve the problem for each subarray, that is, for each pair of integers (l, r) such that (1 ≤ l ≤ r ≤ ), find the maximum number of trees in a forest that can be generated if we use only the values in the range [l, r] in their order, given that you are allowed to remove at most one element from the range.
Instead of printing too many numbers, print the sum of the answers for all subarrays.
The first line of input contains a single integer n (1 ≤ n ≤ 5000), the size of the array.
The second line contains n *distinct* integers A1, A2, ..., An (1 ≤ Ai ≤ n), representing the values of the array.
Print a single integer that represents the sum of the answers for all subarrays.
We have 6 subarrays:
- Three subarrays of size one, the answer for each of them is 1 as we can't get more trees by removing an element.
- Subarray [3, 1], number of generated trees is 1, and if we remove any of the two elements it won't change.
- Subarray [1, 2], number of generated trees is 2 (each of a single node), and if we remove any of the two elements it will become 1, so it is better not to remove any element.
- Subarray [3, 1, 2], number of generated trees is 1, but if we remove the first element, we will get a forest of two trees. So the answer for this subarray is 2.
Total answer is 8 = 1 + 1 + 1 + 1 + 2 + 2.
## Input
The first line of input contains a single integer n (1 ≤ n ≤ 5000), the size of the array.The second line contains n *distinct* integers A1, A2, ..., An (1 ≤ Ai ≤ n), representing the values of the array.
## Output
Print a single integer that represents the sum of the answers for all subarrays.
[samples]
## Note
We have 6 subarrays:- Three subarrays of size one, the answer for each of them is 1 as we can't get more trees by removing an element.- Subarray [3, 1], number of generated trees is 1, and if we remove any of the two elements it won't change.- Subarray [1, 2], number of generated trees is 2 (each of a single node), and if we remove any of the two elements it will become 1, so it is better not to remove any element.- Subarray [3, 1, 2], number of generated trees is 1, but if we remove the first element, we will get a forest of two trees. So the answer for this subarray is 2.Total answer is 8 = 1 + 1 + 1 + 1 + 2 + 2.
**Definitions**
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of $ n $ distinct integers.
For a subarray $ A[l:r] = (a_l, a_{l+1}, \dots, a_r) $, define $ f(l, r) $ as the maximum number of trees in a forest generated from $ A[l:r] $ under the following rule:
- A forest is generated by recursively splitting the subarray at the position of the maximum element; each split produces two independent subproblems (left and right), and each non-empty subarray forms one tree.
- You are allowed to remove **at most one element** from $ A[l:r] $ to maximize the number of trees.
**Constraints**
1. $ 1 \leq n \leq 5000 $
2. $ a_i \in \{1, 2, \dots, n\} $, all distinct
**Objective**
Compute:
$$
\sum_{l=1}^{n} \sum_{r=l}^{n} \max\left( f(l, r), \max_{i \in \{l, \dots, r\}} f(l, r \setminus \{i\}) \right)
$$
where $ f(l, r \setminus \{i\}) $ denotes the number of trees in the forest generated from $ A[l:r] $ with element $ a_i $ removed.