#A0109. 卡片左移

卡片左移

题目背景

小林把 nn 张卡片从左到右排成一行,第 ii 张卡片上写着整数 aia_i。不同的卡片可能写着相同的整数。

小林准备进行一次调整。他想知道,调整后,卡片上的数字从左到右可以组成多少种不同的序列。

题目描述

给定一个长度为 nn 的整数序列 aa。你必须恰好进行一次以下操作:

选择两个下标 l,rl,r,满足 1≤l≤r≤n1\le l\le r\le n,将原来位于第 rr 个位置的元素取出,插入到原来第 ll 个元素的前面。也就是说,将序列变为

$$(a_1,\ldots,a_{l-1},a_r,a_l,a_{l+1},\ldots,a_{r-1},a_{r+1},\ldots,a_n)。$$

当 l=rl=r 时,规定序列保持不变。其余元素的相对顺序不变。

求通过一次上述操作,可以得到多少种不同的数字序列。

两个结果不同,当且仅当存在某个位置,它们在该位置上的数字不同。即使选择的下标不同,只要最后得到的数字序列相同,就只能计算一次。

输入格式

从标准输入读入数据。

第一行包含一个整数 nn。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,相邻整数之间用一个空格隔开。

输出格式

向标准输出输出一个整数,表示不同结果的数量。

答案不需要取模。请注意答案可能超出 32 位有符号整数的表示范围。

样例

3
1 2 1
3

解释

可以得到且仅能得到以下三种序列:

  • (1,2,1)(1,2,1):选择 l=r=1l=r=1;
  • (2,1,1)(2,1,1):选择 l=1,r=2l=1,r=2;
  • (1,1,2)(1,1,2):选择 l=2,r=3l=2,r=3。

选择 l=1,r=3l=1,r=3 也会得到 (1,1,2)(1,1,2),因此不应重复计数。

5
1 1 1 1 1
1

解释

无论选择哪两个合法下标,得到的数字序列都相同。

6
1 4 1 4 2 1
12
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
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

数据范围与子任务

对于所有测试数据,保证:

  • 1≤n≤2×1051\le n\le 2\times 10^5;
  • 1≤ai≤n1\le a_i\le n;
  • 所有输入均为整数。

本题采用子任务捆绑测试:只有通过某个子任务中的全部测试点,才能获得该子任务的全部分数。

子任务编号 分值 nn 的上限 额外性质
1 10 88 无
2 15 100100
3 20 30003000
4 10 2×1052\times10^5 所有 aia_i 两两不同
5 15 a1≤a2≤⋯≤ana_1\le a_2\le\cdots\le a_n
6 30 无