Алтанзул яг n хоног интернэт дээр бизнес хийж хэсэг мөнгө олохоор шийджээ. Тэр i-р өдөр (1≤i≤n) ai мөнгө олдог. Алтанзул ахиц дэвшилтэй прогресст дуртай учраас тэрээр хамгийн их өсөх ai дарааллын уртыг мэдэхийг хүсчээ. Хэрвээ дэд дарааллын бүх тоонууд өсөх дараалалтай байвал үүнийг үл буурах дараалал гэнэ. Алтанзулд энэ өсөх дарааллын уртыг мэдэхэд туслана уу!
Эхний мөрөнд Алтанзулын ажилсан өдрийн тоог агуулсан бүхэл тоо n өгөгдөнө.
Хоёр дах мөрөнд n ширхэг a1, a2, ..., an тоо өгөгдөнө. Энэ нь өдөр бүрийн олсон мөнгөний тоо юм.
Хариулт болох нэг бүхэл тоог хэвлэнэ.
1≤n≤105
1≤ai≤109
6 2 2 1 3 4 1
3
3 2 2 9
3