AT_abc436_f [ABC436F] Starry Landscape Photo

AtCoder 星から見える夜空には $ N $ 個の星があり、これらの $ N $ 個の星は東から西へ一直線上に並んでいます。 東から $ i $ 番目 $ (1\le i\le N) $ の星は、これらの星の中で $ B _ i $ 番目に明るい星です。 高橋くんは、次のような手順で夜空の写真を撮ることにしました。 1. $ 1\le l\le r\le N $ を満たす整数の組 $ (l,r) $ を選び、東から $ l $ 番目、 $ l+1 $ 番目、 $ \ldots $ 、 $ r $ 番目の星が全てフレームに収まり、他の星がフレームに入らないようにカメラを設置する。 2. $ 1\le b\le N $ を満たす整数 $ b $ を選び、 $ N $ 個の星のうち明るさが $ 1 $ 番目から $ b $ 番目に入る（かつフレームに収まっている）星がすべて写り、そうでない星が写らないようにシャッターを開放する。 ただし、星が $ 1 $ つも写らないように写真を撮ることはできません。 このようにして撮影された夜空の写真に写っている星の集合としてありえるものが何通りあるか求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ B _ 1 $ $ B _ 2 $ $ \ldots $ $ B _ N $

答えを出力せよ。

### Sample Explanation 1 例えば $ (l,r)=(2,4),b=3 $ とすると、東から $ 2 $ 番目の星と東から $ 4 $ 番目の星の $ 2 $ つの星が写った写真を撮ることができます。 これを含め、以下の $ 12 $ 通りの星の集合が写った写真を撮ることができます。 それぞれの写真ではより東にある星がより左側に並んでおり、 $ i $ 番目に明るい星に整数 $ i $ が書かれています。  これ以外の集合を撮ることはできないため、`12` を出力してください。 ### 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) $ - 入力はすべて整数