คุณกำลังแข่งแบบล็อกเอาต์ กฎง่ายมาก: เป็นการแข่งขันหนึ่งต่อหนึ่ง มีโจทย์ $n$ ข้อที่กำหนดคะแนนต่างกัน ผู้เข้าแข่งขันคนแรกที่ส่งคำตอบของโจทย์ผ่านเท่านั้นที่จะได้คะแนน แม้อีกคนจะช้าไปเพียง 1 วินาทีก็ไม่ได้คะแนนใด ๆ เพื่อความง่าย เราจะไม่กำหนดเวลาจำกัดหรือการชนะก่อนจบ การแข่งขันดำเนินต่อไปจนกว่าแต่ละโจทย์จะมีผู้เข้าแข่งขันอย่างน้อยหนึ่งคนแก้ได้

คุณค่อนข้างเก่ง แต่... คุณกำลังเจอกับ tourist ฉันรู้ว่ามันเป็นหายนะ คงชนะได้ยาก แต่คุณหวังจะฉกคะแนนมาบ้างเพื่อรักษาหน้า หากคุณกับ tourist ทำโจทย์ข้อเดียวกัน แน่นอนว่าเขาจะชนะคุณ แต่ถ้าคุณเลือกโจทย์ต่างกัน นี่คือโอกาสของคุณ! คุณจะแก้ข้อนี้ได้ก่อน tourist! แต่จากนั้นเขาจะเข้าสู่โหมดคลั่งและแก้โจทย์ที่เหลือทั้งหมดทันที ได้สักข้อก็ดีกว่าไม่ได้อะไรเลยใช่ไหม?

มานิยามกระบวนการให้ชัดเจนขึ้น ในแต่ละครั้ง คุณและ tourist มีโจทย์ที่ยังไม่ถูกแก้ให้เลือก หากไม่มีโจทย์ที่ยังไม่ถูกแก้เหลืออยู่ เกมจะจบและคุณได้ $0$ คะแนน มิฉะนั้น ทั้งคุณและ tourist ต้องเลือกโจทย์ที่จะทำ โดยไม่รู้ว่าอีกคนเลือกข้อใด หากคุณเลือกข้อเดียวกัน tourist จะแก้ได้ก่อนคุณ และเราจะกลับสู่สถานะเริ่มต้นแบบเดิมโดยมีโจทย์เหลือน้อยลง มิฉะนั้น คุณจะได้คะแนนของโจทย์ที่เลือก แต่เกมจะจบทันทีเพราะ tourist แก้โจทย์ที่เหลือทั้งหมดได้ทันที

คุณต้องการทำให้คะแนนที่คุณได้มากที่สุด ส่วน tourist ต้องการทำให้คะแนนนั้นน้อยที่สุด ผลลัพธ์คาดหมายของเกมเป็นเท่าใด หากทั้งคุณและ tourist เล่นอย่างเหมาะที่สุด?

ข้อมูลนำเข้า

บรรทัดแรกมีจำนวนเต็ม $n$ เพียงจำนวนเดียว ($1\le n\le22$) ซึ่งเป็นจำนวนโจทย์

บรรทัดที่สองมีจำนวนเต็ม $n$ จำนวน $a_i$ ($1\le a_i\le10^9$) ซึ่งเป็นคะแนนของแต่ละโจทย์

ข้อมูลส่งออก

แสดงจำนวนหนึ่งจำนวน ซึ่งเป็นคะแนนคาดหมายของคุณ

คำตอบของคุณจะถือว่าถูกต้องหากความคลาดเคลื่อนสัมบูรณ์หรือสัมพัทธ์ไม่เกิน $10^{-6}$

กล่าวอย่างเป็นทางการ ให้คำตอบของคุณเป็น $a$ และคำตอบของคณะกรรมการเป็น $b$ คำตอบของคุณจะได้รับการยอมรับก็ต่อเมื่อ $\frac{|a-b|}{\max(1,|b|)}\le10^{-6}$

ตัวอย่าง

ข้อมูลนำเข้า 1

2
6 7

ข้อมูลส่งออก 1

3.2307692307692

ข้อมูลนำเข้า 2

3
1 1 1

ข้อมูลส่งออก 2

0.8333333333333

ข้อมูลนำเข้า 3

11
1 2 3 4 5 6 7 8 9 10 11

ข้อมูลส่งออก 3

9.4422713866103

หมายเหตุ

สังเกตว่าในตัวอย่างแรก tourist สามารถชนะการแข่งขันได้แน่นอนหากเลือกโจทย์ที่สองเสมอ และเมื่อเจอกลยุทธ์นี้ คุณสามารถเลือกโจทย์แรกเสมอและได้ $6$ คะแนน แต่ tourist จะเล่นอย่างเหมาะที่สุดเพื่อทำให้คะแนนคาดหมายของคุณ น้อยที่สุด ซึ่งบางครั้งอาจหมายถึงการยอมให้คุณชนะการแข่งขัน