[ABC038C] 単調増加

题意翻译

问有多少个子串(不包括空串,其实我觉得应该读子序列)是单调上升的 注意:类似于[1] [8848] [233] 这样一个数字的也属于单调上升的 感谢 @RioBlu 的翻译

题目描述

[problemUrl]: https://atcoder.jp/contests/abc038/tasks/abc038_c $ N $個の数からなる数列が与えられます。$ i $番目の数を$ a_i $と呼びましょう。 $ a_l,a_{l+1},...,a_r $ が単調増加、すなわち $ l≦r $ であって $ a_i\ <\ a_{i+1} $ が$ l≦i\ <\ r $ を満たす全ての$ i $に対して成り立つような$ (l,r) $の数を求めてください。

输入输出格式

输入格式


入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ a_2 $ … $ a_N $

输出格式


$ a_l,a_{l+1},...,a_r $ が単調増加となるような$ (l,r) $の数を $ 1 $ 行に出力せよ。

输入输出样例

输入样例 #1

5
1 2 3 2 1

输出样例 #1

8

输入样例 #2

4
1 2 3 4

输出样例 #2

10

输入样例 #3

6
3 3 4 1 2 2

输出样例 #3

8

输入样例 #4

6
1 5 2 3 4 2

输出样例 #4

10

说明

### 制約 - $ 1≦N≦10^5 $ - $ 1≦a_i≦10^5 $ - $ a_i $は全て整数である ### 部分点 - $ N\ ≦\ 3,000 $ を満たすテストケース全てに正解した場合、部分点として$ 40 $点が与えられる。 ### Sample Explanation 1 条件を満たす$ (l,r) $は$ (1,1),(1,2),(1,3),(2,2),(2,3),(3,3),(4,4),(5,5) $の$ 8 $つです。 ### Sample Explanation 2 $ 1≦l≦r≦N $を満たす$ (l,r) $全てが条件を満たします。 ### Sample Explanation 3 例えば、$ 3,\ 3,\ 4 $はこの問題で単調増加ではないことに注意してください。