QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100
[+1]

# 8945. 区间计数

Statistics

题目描述

给定一个长度为 n 的整数序列 a1,a2,,an,其中每个元素不小于 1、不大于 n,且 1n 中每个数字最多出现两次

称两个可重集合 S,T 相同当且仅当对于任意 xST ,其在 ST 中出现次数相同;反之,两个可重集合 S,T 不同当且仅当存在 xST,其在 ST 中出现次数不同。

称可重集合 S{1,1,2,2,,n,n} 合法当且仅当存在一个区间 [l,r] (1lrn),使得可重集合 T={al,al+1,,ar}S 相同。

你需要求出存在多少个不同的合法可重集合。

输入格式

从标准输入读入数据。

第一行包含一个正整数 n,表示序列长度。

第二行包含 n 个由空格隔开的正整数 a1,a2,,an,描述序列。

输出格式

输出到标准输出。

输出一行一个整数,表示不同的合法可重集合数量。

样例

输入

5
1 2 3 1 3

输出

11

解释

合法可重集合有如下 11 种。

{1},{2},{3},{1,2},{1,3},{2,3},{1,3,3},{1,2,3},{1,1,2,3},{1,2,3,3},{1,1,2,3,3}

样例

输入

12
1 2 3 4 5 6 5 6 4 3 2 1

输出

50

子任务

对于所有测试数据,1n5×1051ain。保证序列中每种数字出现不超过两次。

Subtask 1 (5pts):n100

Subtask 2 (15pts):n5000

Subtask 3 (25pts):n2×105,特殊性质 1。

Subtask 4 (25pts):n2×105,特殊性质 2。

Subtask 5 (30pts):无特殊限制。

特殊性质 1:ai 由另一序列 b1,b2,,bn 进行如下变换而来:

  • 对于每个 1in,独立均匀随机生成一个权值 pi[in103,in+103]
  • 序列 a 是由序列 b 按照权值 p 从小到大排序的结果。即对于每个 i[1,n],令 j 满足 pjp1,p2,,pn 中第 i 小的值,那么有 ai=bj

特殊性质 2:保证 n 是偶数。保证 an2=n,且 a1,a2,,an2 中的数字各不相同,an2,an2+1,,an 中的数字也各不相同。