Background

Special for beginners, ^_^

Description

有 N 个人，每个人有一个身高，他们排成一条直线，求有多少对人能够互相看到对方。 看到对方的条件为：两个人相邻或两个人之间不存在任何人比他们高。

Format

Input

第一行为 N，表示有 N（1<=N<=500,000）个人。以下第 i+1 至 N+1 行，每行一个整数， 表示第 i 个人的身高（小于 2^31）。.

Output

符合条件的对数。

Samples

7
2
4
1
2
2
5
1

10

Limitation

1s, 1024KiB for each test case.