AT_iroha2019_day4_k 世界線

[problemUrl]: https://atcoder.jp/contests/iroha2019-day4/tasks/iroha2019_day4_k

入力は以下の形式で標準入力から与えられる。 > $ N $ $ p_1 $ $ p_2 $ ... $ p_N $

答えを出力してください。

### 制約 - 入力はすべて整数 - $ 1\ \leq\ N\ \leq\ 2\times\ 10^5 $ - $ p_1\ =\ N $ - $ p_1,p_2,...,p_N $ は $ \{1,...,N\} $ の順列 ### 解説 [解説](https://img.atcoder.jp/iroha2019-day4/editorial-K.pdf) ### Sample Explanation 1 この順列を生み出す操作の方法は以下に示した列の変化を実現する$ 3 $通りです。 ・$ {4}→{4,3}→{4,2,3}→{4,2,3,1} $ ・$ {4}→{4,3}→{4,3,1}→{4,2,3,1} $ ・$ {4}→{4,1}→{4,3,1}→{4,2,3,1} $ ### 入力例 2 ``` 4 4 3 2 1 ``` ### 出力例 2 ``` 6 ``` ### 入力例 3 ``` 7 7 6 3 4 1 2 5 ``` ### 出力例 3 ``` 36 ``` ### 入力例 4 ``` 30 30 4 26 15 21 19 14 8 12 7 16 20 2 5 25 13 3 23 18 29 10 27 1 28 9 6 11 24 22 17 ``` ### 出力例 4 ``` 321470237 ``` - - - - - - ### 解説 \[解説\](https://img.atcoder.jp/iroha2019-day4/editorial-K.pdf) ### Sample Explanation 2 \### 入力例 3 ``` 7 7 6 3 4 1 2 5 ``` ### 出力例 3 ``` 36 ``` ### 入力例 4 ``` 30 30 4 26 15 21 19 14 8 12 7 16 20 2 5 25 13 3 23 18 29 10 27 1 28 9 6 11 24 22 17 ``` ### 出力例 4 ``` 321470237 ``` - - - - - - ### 解説 \[解説\](https://img.atcoder.jp/iroha2019-day4/editorial-K.pdf)