At a carnival, n children stand in a row, and child i has an integer skill rating r[i]. Ribbons are handed out under two rules: every child receives at least one ribbon, and any child whose rating is strictly greater than an immediately adjacent neighbour's rating must receive strictly more ribbons than that neighbour. (Equal-rated neighbours have no constraint between them.)
Find the minimum total number of ribbons that satisfies both rules.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the ratings in row order.
Output format
A single integer: the minimum total number of ribbons.
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ r[i] ≤ 1000000000