向左移动一张牌
题目描述
给定一个长度为 N 的正整数序列 A=(A1,A2,…,AN)。
对序列 A 恰好执行一次以下操作:
- 选择 A 中的一个元素,把它取出;
- 把它插入剩余序列中它原来的位置或更靠前的位置。
更形式化地,依次执行以下两步:
- 选择满足 1≤i≤N 的整数 i,令长度为 N−1 的序列 X=(X1,X2,…,XN−1) 为
$(A_1,A_2,\ldots,A_{i-1},A_{i+1},A_{i+2},\ldots,A_N)$,并令整数 Y=Ai。
- 选择满足 1≤j≤i 的整数 j,令长度为 N 的序列
$(X_1,X_2,\ldots,X_{j-1},Y,X_j,X_{j+1},\ldots,X_{N-1})$ 成为新的 A。
注意在有些情况下,元素可以被插入序列的最左端或最右端。
求操作后能得到多少个不同的序列。即使操作中选择的 (i,j) 不同,只要得到的序列相同就只算一个。
输入格式
输入第一行为一个整数 N。
第二行为 N 个整数 A1,A2,…,AN。
输出格式
输出一行一个整数,表示操作后能得到的不同序列的个数。
6
1 4 1 4 2 1
12
样例 1 解释
例如取 i=6,j=4,可以得到 (1,4,1,1,4,2)。
除此之外,还可以得到下面 11 个序列:
- (1,1,4,1,4,2)
- (1,1,4,4,2,1)
- (1,2,4,1,4,1)
- (1,4,1,2,4,1)
- (1,4,1,4,1,2)
- (1,4,1,4,2,1)
- (1,4,2,1,4,1)
- (1,4,4,1,2,1)
- (2,1,4,1,4,1)
- (4,1,1,4,2,1)
- (4,1,4,1,2,1)
因此输出 12。
5
1 1 1 1 1
1
样例 2 解释
不同的 (i,j) 得到的序列如果相同就只算一个。
30
24 22 18 20 14 22 14 14 26 14 26 26 20 22 24 18 22 22 14 24 18 14 14 24 22 18 18 26 14 20
303
数据范围
对于所有测试数据,保证:
- 1≤N≤2×105;
- 1≤Ai≤N;
- 所有输入值均为整数。
子任务
本题共 20 个测试点,按测试点计分:
| 测试点 |
分值 |
每个测试点 |
特殊性质 |
| 1∼6 |
30 |
5 |
N≤2000 |
| 7∼20 |
70 |
无特殊限制 |
每个测试点单独评分,全部测试点的得分之和即为本题得分。