C. Sorting Subarrays
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an array of integers. You perform the following action exactly once: choose a non-empty subsegment of the array and order its elements in non-decreasing order.

How many different arrays can you obtain? A subsegment of an array is a collection of several consecutive elements.

Input

The first line contains a single integer $$$n$$$ — the size of the array ($$$1 \le n \le 200\,000$$$).

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ... $$$a_n$$$ — the contents of the array ($$$1 \le a_i \le 10^9$$$).

Output

Output a single integer — the number of different arrays you can obtain by sorting a subsegment once.

Scoring
SubtaskPointsConstraints
113$$$n \le 50$$$
226$$$n \le 3\,000$$$
322$$$1 \le a_i \le 2$$$
439No additional constraints
Examples
Input
7
3 1 4 1 5 9 2
Output
8
Input
4
1 2 3 4
Output
1
Note

Listed below are all eight achievable arrays in the first example. Square brackets indicate the sorted subsegment.

  1. $$$[3], 1, 4, 1, 5, 9, 2 \rightarrow 3, 1, 4, 1, 5, 9, 2$$$
  2. $$$[3, 1], 4, 1, 5, 9, 2 \rightarrow 1, 3, 4, 1, 5, 9, 2$$$
  3. $$$[3, 1, 4, 1], 5, 9, 2 \rightarrow 1, 1, 3, 4, 5, 9, 2$$$
  4. $$$[3, 1, 4, 1, 5, 9, 2] \rightarrow 1, 1, 2, 3, 4, 5, 9$$$
  5. $$$3, [1, 4, 1], 5, 9, 2 \rightarrow 3, 1, 1, 4, 5, 9, 2$$$
  6. $$$3, [1, 4, 1, 5, 9, 2] \rightarrow 3, 1, 1, 2, 4, 5, 9$$$
  7. $$$3, 1, 4, [1, 5, 9, 2] \rightarrow 3, 1, 4, 1, 2, 5, 9$$$
  8. $$$3, 1, 4, 1, 5, [9, 2] \rightarrow 3, 1, 4, 1, 5, 2, 9$$$