AT_agc029_c [AGC029C] Lexicographic constraints

[problemUrl]: https://atcoder.jp/contests/agc029/tasks/agc029_c $ N $ 個の文字列が一列に並んでおり、どの隣り合う $ 2 $ つの文字列に対しても、 左に書いてある文字列の方が右に書いてある文字列よりも辞書順で小さいことが分かっています。 つまり、左から $ i $ 番目の文字列を $ S_i $ としたときに、辞書順で $ S_1\

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 2\times\ 10^5 $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ - $ A_i $ は整数 ### Note 文字列は英字アルファベットからなる必要はない。無限に多くの文字があり、辞書式順序がそれらについて定まっているとして良い。 ### Sample Explanation 1 例えば、$ S_1= $`abc`, $ S_2= $`bb`, $ S_3= $`c` のときは$ S_1,S_2,...,S_N $ に含まれる文字の種類数は $ 3 $ になります。 しかし、文字列をうまく選ぶと、文字の種類数を $ 2 $ にすることができます。