Trophies

题号：NC19785
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

蒜头的家里有一张长长的桌子，桌子上有n个奖杯排成一排。我们用x_i表示第i个奖杯的高度。奖杯的高度两两不同，为了方便，我们保证x是一个 $1\sim n$ 的排列。

由于蒜头的桌子已经放不下新的奖杯了，他打算将一些奖杯送给修修和栋栋。具体来说，他打算选择四个参数l₁,r₁,l₂,r₂ (1 ≤ l₁ ≤ r₁ < l₂ ≤ r₂ ≤ n),

然后将区间[l₁,r₁]中的奖杯送给修修，将区间[l₂,r₂]中的奖杯送给栋栋。
修修不希望他拿到的奖杯中最矮的一个比栋栋拿到的奖杯中最高的一个还要高，因此他想知道有多少种方案满足 $\min\limits_{l_1\leq i\leq r_1}x_i\leq\max\limits_{l_2\leq j\leq r_2}x_j$ 。

输入描述:

第一行一个整数n (1 ≤ n ≤ 10⁶)，第二行n个整数 (1 ≤ x_i≤ n)。

输出描述:

输出一行一个整数表示方案数。

示例1

输入

复制

5
1 4 3 5 2

输出

复制