Հիստոգրամի ամենամեծ ուղղանկյուն մակերեսը
Ձեզ տրված են
n թվեր, որոնք ցույց են տալիս հիստոգրամի սյուների բարձրությունները։ Պահանջվում է հաշվել այն առավելագույն մակերեսը, որը հնարավոր է ստանալ հիստոգրամի ներսում՝ առանց դուրս գալու սյուների սահմաններից:Հիստոգրամի բոլոր սյուները ունեն 1 լայնություն, իսկ դրանց բարձրությունները կամայական ոչ բացասական ամբողջ թվեր են:
Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ ):Հաջորդ տողում տրված են
n բացատով բաժանված թվեր a_1, a_2, ..., a_n (0 ≤ ≤ ):Ելք
Ծրագիրը պետք է տպի այն առավելագույն մակերեսը, որը հնարավոր է ստանալ հիստոգրամի սյուներից:
Օրինակներ
Մուտք | Ելք |
8
6 2 5 4 5 1 6 1 | 12 |
Հուշում
Հիստոգրամի յուրաքանչյուր տարրի համար կարելի է հաշվել 2 արժեք՝ ձախ կողմում գտնվող ամենամոտ տարրն, որը փոքր է տվյալ տարրից, և աջ կողմում գտնվող ամենամոտ տարրն, որը նույնպես փոքր է տվյալ տարրից։ Այդ երկու արժեքները հերիք են հաշվելու այն ուղղանկյույթի մակերեսը, որի բարձրությունը հավասար է տվյալ սյան բարձրությանը:
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB