一群人排成一列。每个人的身高各不相同。你想要计算队列中满足以下条件的无序对的数量：这对人中的每一个人都比他们之间队列里的所有人都要高。
更正式地说，令 $d$ 为从左到右的人的身高序列。我们想要计算满足 $i < j$ 且对于所有满足 $i < k < j$ 的 $k$，都有 $d_i > d_k$ 且 $d_j > d_k$ 的下标对 $(i, j)$ 的数量。注意，如果 $j = i + 1$（即 $i$ 和 $j$ 之间没有 $k$），该条件显然成立。
输入格式
输入的第一行包含一个整数 $n$ ($2 \le n \le 10^6$)，表示人数。
接下来的 $n$ 行，每行包含一个整数 $d_i$ ($1 \le d_i \le n$)。这些是队列中人们的身高，按他们站立的顺序排列。该序列保证是 $1$ 到 $n$ 的一个排列。
输出格式
输出一个整数，表示比他们之间所有人都要高的人对的数量。
样例
样例输入 1
3 2 1 3
样例输出 1
3
样例输入 2
6 1 3 2 6 4 5
样例输出 2
7