← 返回题目列表

AtCoder · abc390_f

I. 双和 3

中文机器翻译题面 查看原题

分数: 525 点

问题陈述

给你一个整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N.

对于每个整数对 (L,R) 与 1 \le L \le R \le N,定义 f(L,R) 如下:

  • 从一块空黑板开始。写下 黑板上按顺序 R-L+1 整数 A_L, A_{L+1}, \ldots, A_R 。
  • 重复以下操作,直到黑板上的所有整数都被擦除:
    • 选择整数 l, r 与 l \le r 这样每个整数 l 通过 r 在黑板上至少出现一次。然后,删除所有整数 黑板上的 l 通过 r 。
  • 让 f(L,R) 是从黑板上擦除所有整数所需的此类操作的最少数量。

查找 \displaystyle \sum_{L=1}^N \sum_{R=L}^N f(L,R).

约束

  • 1 \le N \le 3 \times 10^5
  • 1 \le A_i \le N
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \ldots A_N

输出

打印答案。


示例输入 1

4
1 3 1 4

示例输出 1

16

例如,在以下情况 (L,R)=(1,4):

  • 黑板上有 1,3,1,4.
  • 选择 (l,r)=(1,1) 并删除所有出现的 1。现在黑板上有 3,4.
  • 选择 (l,r)=(3,4) 并删除所有出现的 3 和 4。黑板变成空的。
  • 它不能通过少于两次操作完成,所以 f(1,4) = 2.

同样,你可以找到 f(2,4)=2, f(1,1)=1等

\displaystyle \sum_{L=1}^N \sum_{R=L}^N f(L,R) = 16,所以打印 16.


示例输入 2

5
3 1 4 2 4

示例输出 2

23

示例输入 3

10
5 1 10 9 2 5 6 9 1 6

示例输出 3

129