# [ABC390F] Double Sum 3

## 题面翻译

### 题目描述
给你一个长为 $N$ 的整数序列 $A=(A_1,A_2, \dots A_N)$。\
定义 $f(L,R)$ 如下
- 从一块空黑板开始。在黑板上依次写下 $R−L+1$ 个整数 $A_L,A_{l+1}, \dots,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)$。
### 输入格式
第一行一个正整数 $N$。第二行 $N$ 个正整数 $A_1,A_2,\dots,A_N$。
### 输出格式
输出一行，即所求答案。
### 样例1解释
以 $(L,R)$ 为例。\
黑板上有 $1,3,1,4$。\
选择 $(L,R)=(1,1)$ 并擦除所有 $1$。现在黑板上有 $(3,4)$。\
选择 $(L,R)=(3,4)$ 并擦除所有 $3$ 和 $4$。黑板就变成空的了。\
不能少于 $2$ 次操作完成。\
$\displaystyle \sum_{L=1}^N \sum_{R=L}^N f(L,R)=16$，所以打印 $16$。

## 题目描述

[problemUrl]: https://atcoder.jp/contests/abc390/tasks/abc390_f

長さ $ 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) $ を求めてください。

## 输入格式

入力は以下の形式で標準入力から与えられる。

> $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

## 输出格式

答えを出力せよ。

## 样例 #1

### 样例输入 #1

4 1 3 1 4

### 样例输出 #1

16

## 样例 #2

### 样例输入 #2

5 3 1 4 2 4

### 样例输出 #2

23

## 样例 #3

### 样例输入 #3

10 5 1 10 9 2 5 6 9 1 6

### 样例输出 #3

129

## 提示

### 制約

- $ 1\le\ N\le\ 3\times\ 10^5 $
- $ 1\le\ A_i\le\ N $
- 入力される値は全て整数

### Sample Explanation 1

例えば $ (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 $ を出力してください。

• 从一块空黑板开始。在黑板上依次写下 $R−L+1$ 个整数 $A_L,A_{l+1}, \dots,A_R$

改为：

• 从一块空黑板开始。在黑板上依次写下 $R−L+1$ 个整数 $A_L,A_{L+1}, \dots,A_R$

- 从一块空黑板开始。在黑板上依次写下 $R−L+1$ 个整数 $A_L,A_{L+1}, \dots,A_R$

貌似管理都休假了。祝洛谷用户新春佳节快乐，心想事成！