C - 単調増加 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N個の数からなる数列が与えられます。i番目の数をa_iと呼びましょう。

a_l,a_{l+1},...,a_r が単調増加、すなわち l≦r であって a_i<a_{i+1}l≦i<r を満たす全てのiに対して成り立つような(l,r)の数を求めてください。


制約

  • 1≦N≦10^5
  • 1≦a_i≦10^5
  • a_iは全て整数である

部分点

  • N ≦ 3,000 を満たすテストケース全てに正解した場合、部分点として40点が与えられる。

入力

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

N
a_1 a_2a_N

出力

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


入力例1

5
1 2 3 2 1

出力例1

8

条件を満たす(l,r)(1,1),(1,2),(1,3),(2,2),(2,3),(3,3),(4,4),(5,5)8つです。


入力例2

4
1 2 3 4

出力例2

10

1≦l≦r≦Nを満たす(l,r)全てが条件を満たします。


入力例3

6
3 3 4 1 2 2

出力例3

8

例えば、3, 3, 4はこの問題で単調増加ではないことに注意してください。


入力例4

6
1 5 2 3 4 2

出力例4

10