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