尔哲星上新建了N个通信柱。通信模块设计在通信柱的顶端。由于设计的关系，每个通信柱只会与在它之前且不比它高，或者在它之后不比它低的通信柱通信。

工程师小曹想知道，所有通信柱都开启之后，有多少对通信柱可以建立通信。

如图中，高分别为3、5、2、1、4的通信柱，可以形成4次通信：3-5,3-4,2-4,1-4。

输入有多组数据。

每组数据一行，以一个正整数N开始（1<=N<=100000)。接下来N个正整数x，1<=x<=500000，代表每个通信柱的高度。

对于30%的数据，1<=N<=1000。

对于100%的数据，1<=N<=100000。

每组数据输出一行答案。