24158번 - ビルの飾りつけ (Building) 다국어

国際情報オリンピックが日本で開かれることとなり，世界の選手達を歓迎するため，空港か ら宿泊施設までの道沿いにある高層ビルを飾りつけることにした．ある著名なデザイナーにデ ザインを依頼したところ，飾りつけに利用するビルは，空港から宿泊施設に向けて高くなって いく必要があると言った．つまり，飾りつけに利用するビルの高さを，空港に近いものから順 に h₁, h₂, h₃, · · · とおくと，h₁ < h₂ < h₃ < · · · となっていなければならない．

できるだけ飾りつけを華やかにするため，飾りつけに利用するビルの数をできるだけ多くし たい．入力として全てのビルの高さが与えられたとき，利用することのできるビルの数の最大 値を計算するプログラムを作れ．

入力の 1 行目には，1 つの整数 n (1 ≤ n ≤ 1000) が書かれてい る．これは，空港から宿泊施設までの道のりにあるビルの数が n であることを表す．

次の n 行には，それぞれのビルの高さが書かれてる．i + 1 行目 (1 ≤ i ≤ n) には 1 つの整数 a_i(1 ≤ a_i ≤ 10000) が書かれている．これは，空港から i 個目のビルの高さが ai であることを 表す．

出力は，標準出力に行うこと．飾りつけに利用することのできるビルの数の最大値 を表す整数を出力せよ．

ビルの総数が 9 であり、高さが空港に近いものから順に 3, 7, 5, 9, 8, 10, 10, 11, 9 である場合 を示したのが下図である。色をつけて示したビルを選ぶことにより、飾り付けに利用するビル の数を最大にすることができる。このときの最大値は 5 である。