K. Good Subarrays
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ consisting of $$$n$$$ distinct integers.

A array $$$b$$$ is called good if it can be sorted in non-decreasing order by performing the following operation at most once:

  • Choose one or more non-intersecting subarrays of the array $$$b$$$, and reverse each of them.

In other words, you may select several disjoint segments within the array and reverse each of them, at most once in total. If after these reversals the subarray becomes sorted, it is considered good.

Your task is to determine the number of good subarrays in the given array.

Input

The first line contains a single integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — the length of the array $$$a$$$.

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

Output

Print a single integer — the number of good subarrays.

Example
Input
3
2 3 1
Output
5