题目描述

薯条哥有 $n$ 个点，第 $i$ 个点的权值为 $w_i$ 。

现在，薯条哥想要用这 $n$ 个点建图。

但是建好的图要满足如果存在三个点 $a,b,c$ ，有边 a-b 和边 b-c ，那么不能有 $w_a\le w_b\le w_c$ 。

现在，薯条哥想问你，建好的图上最多可以有多少条边。

输入描述

第一行输入一个整数 $n(2 \le n \le 10^5)$，表示点数。

第二行输入$n$ 个整数表示每个点的权值，第 $i$ 个数为 $w_i(1 \le w_i \le 10^5)$

输出描述

输出一个整数，表示建好的图上最多可以有多少条边。

样例

输入

4
1 2 3 4

输出

4

样例解释

可以连 1-3, 2-3, 1-4 和 2-4 这四条边。