Count the Number of Incremovable Subarrays II

Given an array of positive integers, removing one non-empty contiguous subarray is a valid removal if the remaining array (which may be empty) is strictly increasing. Count all valid removals.

The standard input/output, the ranges added by this site, and the examples follow this problem's description.

输入格式

The first line contains n (1≤n≤100000); the second line contains n positive integers, 1≤nums[i]≤10^9. The ranges are taken from the original problem's constraints.

输出格式

Output the number of valid contiguous subarrays, stored as a 64-bit integer.

样例 1

输入：

4
1 2 3 4

输出：

10

样例 2

输入：

4
6 5 7 8

输出：

7

样例 3

输入：

4
8 7 6 6

输出：

3