405110: GYM101798 E Forest (C)

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 A₁, A₂, ..., A_n (1 ≤ A_i ≤ n), representing the values of the array.

Print a single integer that represents the sum of the answers for all subarrays.

3
3 1 2

8

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.