Count Good Subsequences

Given an integer array arr. A non-empty subsequence is a sequence obtained by choosing some strictly increasing indices from the array; its values do not need to be in ascending order. A subsequence is good if all of its values are distinct and every integer between its minimum value a and its maximum value b appears in it. Count the good subsequences. Different index choices are counted separately, even if their value sequences are identical. Output the mathematically exact integer, with no modulo. The original interface uses long, but over the full range the answer can exceed 64 bits, and the modulus added in the code on the compiled page has no basis in the statement; this site explicitly corrects both points and keeps all original ranges.

输入格式

The first line contains an integer n, and the second line contains n integers arr[i]. 1≤n≤100000, 1≤arr[i]≤100000; duplicate values and any original order are allowed.

输出格式

Output an exact non-negative decimal integer, with no modulo, no truncation, and no scientific notation. The result may exceed 64 bits and Python's default 4300-digit decimal conversion limit; use arbitrary-precision integers. The answer has at most 30103 decimal digits.

样例 1

输入：

3
2 2 1

输出：

5

样例 2

输入：

2
1 3

输出：

2

样例 3

输入：

3
3 1 2

输出：

6

样例说明

All three public examples are derived by this site from the definition. [2,2,1] has 3 single-element subsequences and 2 subsequences with value set {1,2}, for 5 in total. [1,3] allows only single elements, for 2 in total. [3,1,2] has 3 single elements, 2 ranges of adjacent values, and 1 full range, for 6 in total; the original order of the values does not affect whether a range is validly covered.