问题 H: Insert 1, Insert 2, Insert 3, ...
内存限制:512 MB
时间限制:2.000 S
评测方式:文本比较
命题人:
提交:1
解决:1
题目描述
A sequence a1, a2, . . . , an consisting of positive integers is said to be generatable when one can obtain a
by repeating the following operation on an empty sequence:
• Choose a positive integer k, and insert 1, insert 2, ..., insert k respectively into some position in the
sequence while preserving their relative order. More specifically, let ix be the index of newly inserted
x in the sequence after the operation, then i1 < i2 < · · · < ik.
For instance, a = (1, 1, 2, 2, 1, 1, 3, 4, 2, 3) is generatable. Here is one way to generate it:
() → (1, 2) → (1, 2, 1, 2, 3) → (1, 1, 2, 2, 1, 3, 4, 2, 3) → (1, 1, 2, 2, 1, 1, 3, 4, 2, 3).
You are given a sequence A1, A2, . . . , AN consisting of positive integers. Find the number of pairs of
integers (L, R) such that:
• 1 ≤ L ≤ R ≤ N and the contiguous subsequence AL, . . . , AR is generatable.
输入
The first line contains an integer N (1 ≤ N ≤ 106
).
The second line contains N integers A1, A2, . . . , AN (1 ≤ Ai ≤ N).
输出
Output the number of pairs of integers (L, R) satisfying the conditions.
样例输入 复制
6
1 1 2 2 3 3
样例输出 复制
8
提示
In the first sample, the 8 pairs are: (1, 1),(1, 2),(1, 3),(1, 4),(1, 5),(1, 6),(2, 2),(2, 3).