افتتحت الأبقار عملًا تجاريًا جديدًا، ويريد Farmer John معرفة مدى نجاحها. يعمل المشروع منذ $N$ ($1 \leq N \leq 100{,}000$) يومًا، وفي كل يوم $i$ سجلت الأبقار صافي أرباحها $P_i$ ($-1{,}000 \leq P_i \leq 1{,}000$).

يريد Farmer John إيجاد أكبر ربح إجمالي حققته الأبقار خلال أي فترة زمنية متصلة. (لاحظ أن طول الفترة المتصلة يمكن أن يتراوح من يوم واحد إلى $N$ يومًا.) ساعده بكتابة برنامج لحساب أكبر مجموع للأرباح المتتالية.

الإدخال

اقرأ الإدخال من الإدخال القياسي.

• السطر 1: عدد صحيح واحد، $N$.
• الأسطر $2..N+1$: يحتوي السطر $i+1$ على عدد صحيح واحد، $P_i$.

الإخراج

اكتب الإخراج إلى الإخراج القياسي.

• السطر 1: عدد صحيح واحد يمثل أكبر مجموع للأرباح في أي فترة زمنية متصلة.

أمثلة

الإدخال 1

7
-3
4
9
-2
-5
8
-3

الإخراج 1

14

ملاحظة

يُحصل على أكبر مجموع بجمع الأعداد من الثاني إلى السادس (4 و9 و-2 و-5 و8)، ليكون الناتج 14.

مؤلف المسألة: Neal Wu، 2007