يخطط Farmer John لافتتاح جامعة جديدة للأبقار!

توجد $N$ أبقار ($1 \le N \le 10^5$) قد تلتحق بهذه الجامعة. كل بقرة مستعدة لدفع رسوم دراسية بحد أقصى $c_i$ ($1 \le c_i \le 10^6$). يستطيع Farmer John تحديد الرسوم الدراسية التي يجب أن تدفعها جميع الأبقار للالتحاق. إذا تجاوزت هذه الرسوم الحد الأقصى الذي تقبل بقرة دفعه، فلن تلتحق تلك البقرة بالجامعة. يريد Farmer John كسب أكبر قدر ممكن من المال حتى يتمكن من دفع أجر عادل لمدرسيه. حدد مقدار المال الذي يمكنه كسبه والرسوم الدراسية التي ينبغي أن يفرضها.

الإدخال

يحتوي السطر الأول على $N$. يحتوي السطر الثاني على $N$ أعداد صحيحة $c_1, c_2, \dots, c_N$، حيث $c_i$ هي أكبر رسوم دراسية تقبل البقرة $i$ دفعها.

الإخراج

اطبع أكبر مبلغ يمكن لـFarmer John كسبه والرسوم الدراسية المثلى التي ينبغي أن يفرضها. إذا كانت هناك حلول متعددة، فاطبع الحل ذي أقل رسوم دراسية مثلى.

لاحظ أن كبر الأعداد الصحيحة المستخدمة في هذه المسألة قد يتطلب استعمال أنواع أعداد صحيحة ذات 64 بت (مثل "long" في Java أو "long long" في C/C++).

أمثلة

الإدخال 1

4
1 6 4 6

الإخراج 1

12 4

ملاحظة

إذا فرض Farmer John رسوماً قدرها $4$، فستلتحق $3$ أبقار، مما يتيح له كسب $3 \cdot 4 = 12$.

المهام الفرعية

• تحقق حالات الاختبار من 2 إلى 4 الشرط $c_i \le 1{,}000$.
• تحقق حالات الاختبار من 5 إلى 8 الشرط $N \le 5{,}000$.
• لا توجد قيود إضافية على حالات الاختبار من 9 إلى 12.

مؤلف المسألة: Freddie Tang