• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

فراز در یک بازی شرکت کرده است اما چندان حوصله این بازی را ندارد. شرح بازی به این شکل است که فراز با دو دنباله $a_1, a_2, \dots, a_n,$ و $b_1, b_2, \dots, b_n,$ مواجه است به شکلی که تمامی $a_i$ها مثبت و تمامی $b_i$ها در ابتدا صفر هستند. فراز در هر مرحله از بازی یک $i$ دلخواه انتخاب می‌کند به شکلی که $1 \leq i \leq n$ و سپس به اندازه $a_i$، به $b_i$ اضافه یا کم می‌کند. یعنی قرار می‌دهد $b_i \leftarrow b_i - a_i ,$ یا $b_i \leftarrow b_i + a_i ,$ .

هدف بازی این است که پس از تعدادی مرحله، دنباله $b$ اکیداً صعودی شود. یعنی داشته باشیم $b_1 \lt b_2 \lt \dots \lt b_n$.

فراز که حوصله ندارد، می‌خواهد در کم‌ترین تعداد مرحله به هدف بازی برسد. او که حتی حوصله انجام این کار را هم ندارد از شما پرسیده است که این کم‌ترین تعداد مرحله چند است؟

ورودی

خط اول شامل عدد $n$ است که نشان دهنده طول دو دنباله $a$ و $b$ خواهد بود. $$1 \leq n \leq 5000$$

خط دوم شامل $n$ عدد است که به ترتیب نشان دهنده دنباله $a_1, a_2, \dots, a_n ,$ هستند. $$1 \leq a_i \leq 10^9$$

خروجی

در تنها خط خروجی حداقل مراحل لازم بازی فراز را چاپ کنید.

مثال‌ها

ورودی نمونه ۱

5
1 2 3 4 5

خروجی نمونه ۱

4

ورودی نمونه ۲

7
1 2 1 2 1 2 1

خروجی نمونه ۲

10