/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
AtCoder 星から見える夜空には N 個の星があり、これらの N 個の星は東から西へ一直線上に並んでいます。 東から i 番目 (1\le i\le N) の星は、これらの星の中で B _ i 番目に明るい星です。
高橋くんは、次のような手順で夜空の写真を撮ることにしました。
- 1\le l\le r\le N を満たす整数の組 (l,r) を選び、東から l 番目、l+1 番目、\ldots、r 番目の星が全てフレームに収まり、他の星がフレームに入らないようにカメラを設置する。
- 1\le b\le N を満たす整数 b を選び、N 個の星のうち明るさが 1 番目から b 番目に入る（かつフレームに収まっている）星がすべて写り、そうでない星が写らないようにシャッターを開放する。
ただし、星が 1 つも写らないように写真を撮ることはできません。
このようにして撮影された夜空の写真に写っている星の集合としてありえるものが何通りあるか求めてください。
制約
- 1\le N\le5\times10 ^ 5
- 1\le B _ i\le N\ (1\le i\le N)
- B _ i\ne B _ j\ (1\le i\lt j\le N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N B _ 1 B _ 2 \ldots B _ N
出力
答えを出力せよ。
入力例 1
4 3 1 4 2
出力例 1
12
例えば (l,r)=(2,4),b=3 とすると、東から 2 番目の星と東から 4 番目の星の 2 つの星が写った写真を撮ることができます。
これを含め、以下の 12 通りの星の集合が写った写真を撮ることができます。 それぞれの写真ではより東にある星がより左側に並んでおり、i 番目に明るい星に整数 i が書かれています。
これ以外の集合を撮ることはできないため、12 を出力してください。
入力例 2
7 1 2 3 4 5 6 7
出力例 2
28
入力例 3
20 15 5 13 17 9 11 20 4 14 16 6 3 8 19 12 7 10 18 2 1
出力例 3
627
Score : 500 points
Problem Statement
In the night sky seen from planet AtCoder, there are N stars, and these N stars are arranged in a line from east to west. The i-th star from the east (1\le i\le N) is the B _ i-th brightest among these stars.
Takahashi decided to take a picture of the night sky using the following procedure:
- Choose a pair of integers (l,r) satisfying 1\le l\le r\le N, and set up the camera so that the l-th, (l+1)-th, \ldots, r-th stars from the east all fit in the frame, and no other stars enter the frame.
- Choose an integer b satisfying 1\le b\le N, and open the shutter so that all stars among the N stars whose brightness ranks from 1st through b-th (and that fit in the frame) are captured, and no other stars are captured.
However, he may not take a picture with no stars captured.
Find the number of different sets of stars that can be captured in pictures taken in this way.
Constraints
- 1\le N\le5\times10 ^ 5
- 1\le B _ i\le N\ (1\le i\le N)
- B _ i\ne B _ j\ (1\le i\lt j\le N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N B _ 1 B _ 2 \ldots B _ N
Output
Print the answer.
Sample Input 1
4 3 1 4 2
Sample Output 1
12
For example, with (l,r)=(2,4),b=3, you can take a picture with two stars: the 2nd star from the east and the 4th star from the east.
Including this, you can take pictures with the following 12 different sets of stars. In each picture, stars further east are arranged further left, and the i-th brightest star is labeled with integer i.
No other sets can be captured, so print 12.
Sample Input 2
7 1 2 3 4 5 6 7
Sample Output 2
28
Sample Input 3
20 15 5 13 17 9 11 20 4 14 16 6 3 8 19 12 7 10 18 2 1
Sample Output 3
627