شکلات رویال


  • محدودیت زمان: ۰٫۵ ثانیه
  • محدودیت حافظه: ۵۰ مگابایت
  • محدودیت اعداد: تمامی اعداد ورودی و خروجی از 101810^{18} کوچک‌ترند.

ویلی‌وانکا در مسابقه‌ی بهترین شکلات‌ساز کهکشان راه شیری شرکت کرده و می‌خواهد بهترین شکلات خود که نام‌ش شکلات رویال است را به کمیته‌ی داوری بفرستد تا به آن امتیاز دهند.

توضیح تصویر

در فرآیند تولید هر نوع شکلات، تعدادی دانه‌ی کاکائو مختلف با عطرها و طعم‌های گوناگون به عنوان ماده‌ی اولیه وجود دارد که بنابر ترتیب اضافه شدن آن‌ها به ترکیبات، شکلاتِ نهایی طعم‌های مختلفی خواهد داشت.

اگر ما nn نوع کاکائو با شیرینی‌های مختلف داشته‌باشیم و آن‌ها را به ترتیب {a1,a2,...,an}\{a_1, a_2, ..., a_n\} که aia_i شیرینی دانه‌ی iiم است، به ترکیب اضافه کنیم؛ شکلات رویال ساخته می‌شود.

ویلی‌وانکا می‌داند امتیازی که داوران به شکلات‌ها می‌دهند از فرمولی خاص تبعیت می‌کند: به ازای هر دو دانه‌ای که اولی زودتر از دومی به ترکیب اضافه شده و اولی شیرین‌تر از دومی بوده، حاصل ضرب مقدار شیرینی آن دو به امتیاز اضافه می‌شود. (درواقع امتیاز نهایی برابر با مجموع تمامی این حاصل‌ضرب‌ها به ازای هر دو دانه‌ای‌ست که شرایط گفته‌شده را داشته‌باشند.)

شفاف‌سازی: (i<j)and(ai>aj)ai×aj\sum_{(i<j) and (a_i > a_j)} a_i \times a_j

حال در فرآیند آنالیز شکلات رویال ارسالی به مسابقات، شما اومپا-لومپای مسئول کیفیت هستید که باید امتیاز شکلات رویالی که به شما داده می‌شود را محاسبه کنید.

ورودی🔗

در سطر اول عدد n105n \leq 10^5 — تعداد دانه‌های کاکائو مختلف برای ساختن شکلات رویال آمده‌است.

در سطر دوم nn عدد آمده که iiمی آن‌ها، ai1000|a_i| \leq 1000، شیرینی iiمین دانه‌ی کاکائو است که به ترکیب اضافه می‌شود. هرچه دانه شیرین‌تر باشد، عدد شیرینی‌اش بزرگ‌تر است.

توجه شود که شیرینی 0 یعنی شکلات نه تلخ است و نه شیرین. در نتیجه شیرینی دانه‌های تلخ، عددی منفی‌ست. در میان دانه‌های کاکائو، حداکثر یک دانه‌ی تلخ (با شیرینی منفی قرار دارد).

تضمین می‌شود که امتیاز حاصل از 101810^{18} کوچک‌تر است.

خروجی🔗

یک عدد چاپ شود که امتیاز شکلات رویال مورد تحقیق است.

نمونه‌ی ورودی🔗

5
10 3 6 12 2
Plain text

نمونه‌ی خروجی🔗

152
Plain text

توضیح🔗

امتیاز این شکلات رویال برابر است با:

10×3 + 10×6 + 10×2 + 3×2 + 6×2 + 12×2 = 152
Plain text