/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
1\le L\le R\le N を満たす整数の組 (L,R) に対し f(L,R) を以下のように定義します。
- 何も書かれていない黒板に R-L+1 個の整数 A_L,A_{L+1},\ldots,A_R を順に書き込む。
- 以下の操作を黒板に書かれた整数が全て消えるまで繰り返す。
- 整数 l,r を選ぶ。ただし、 l\le r かつ黒板に l 以上 r 以下の整数が全て 1 つ以上書かれているように 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) の場合、以下の手順で f(L,R) を計算することができます。
- 黒板に 1,3,1,4 が書かれている。
- (l,r)=(1,1) を選び、黒板に書かれた 1 を全て消す。黒板には 3,4 が書かれた状態になる。
- (l,r)=(3,4) を選び、黒板に書かれた 3,4 を全て消す。黒板は何も書かれていない状態になる。
- 2 回未満の操作で黒板の整数を全て消すことはできないので、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
Score : 525 points
Problem Statement
You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.
For each integer pair (L,R) with 1 \le L \le R \le N, define f(L,R) as follows:
- Start with an empty blackboard. Write the R-L+1 integers A_L, A_{L+1}, \ldots, A_R on the blackboard in order.
- Repeat the following operation until all integers on the blackboard are erased:
- Choose integers l, r with l \le r such that every integer from l through r appears at least once on the blackboard. Then, erase all integers from l through r that are on the blackboard.
- Let f(L,R) be the minimum number of such operations needed to erase all the integers from the blackboard.
Find \displaystyle \sum_{L=1}^N \sum_{R=L}^N f(L,R).
Constraints
- 1 \le N \le 3 \times 10^5
- 1 \le A_i \le N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
4 1 3 1 4
Sample Output 1
16
For example, in the case of (L,R)=(1,4):
- The blackboard has 1,3,1,4.
- Choose (l,r)=(1,1) and erase all occurrences of 1. The blackboard now has 3,4.
- Choose (l,r)=(3,4) and erase all occurrences of 3 and 4. The blackboard becomes empty.
- It cannot be done in fewer than two operations, so f(1,4) = 2.
Similarly, you can find f(2,4)=2, f(1,1)=1, etc.
\displaystyle \sum_{L=1}^N \sum_{R=L}^N f(L,R) = 16, so print 16.
Sample Input 2
5 3 1 4 2 4
Sample Output 2
23
Sample Input 3
10 5 1 10 9 2 5 6 9 1 6
Sample Output 3
129