Description

后缀数定义如下： 

1. 一个后缀数是一个不超过n位不小于2位的n进制数。
2. 一个后缀数是一个所有位上的数字都不重复的数
3. 一个后缀数的末尾一定是所有位上的数字中最大的，第一位是所有位上的数字中最小的,第二大的数字到第一位的距离不小于到末尾的距离，倒数第二大的数字到末尾的距离不小于到第一位的距离。
4. 一个后缀数不包含一个后缀数。

现在给定一个很长的数字串，为1到n的一个排列，请算出在数字串中一共有多少后缀数（后缀数可相交，但必须符合不包含等条件）。

Input Format

第一行一个数字 $n$ 表示数字串的长度。

第二行 $n$ 个数字，描述数字串，每个数位用一个空格隔开。

$2\leq n \leq 10^7$

Output Format

一个数字 $ans$，表示总共有 $ans$ 个后缀数。

6
1 2 3 4 5 6

5