संख्याएं हटाने का खेल

आइए एक खेल खेलते हैं। आपके पास n धनात्मक पूर्णांक हैं (यहाँ n सम संख्या है)। प्रत्येक चरण में, आपको अनुक्रम के आरंभ या अंत से एक संख्या हटाने और उसे अपने पास रखने की अनुमति है। मैं (कंप्यूटर) अनुक्रम के पहले और अंतिम तत्व में से जो बड़ा होगा, उसे हटा लूँगा। यदि वे दोनों समान हों, तो मैं पहला तत्व हटा दूँगा। हम बारी-बारी से ऐसा करेंगे, जब तक सूची में कोई आइटम न बचा हो।

यदि आप गेम की शुरुआत करते हैं, तो आपके लिए अधिकतम कितना योग (sum) इकट्ठा करना संभव है?

इनपुट

इनपुट की पहली पंक्ति में एक एकल पूर्णांक n (1 ≤ n ≤ 1000) दिया होता है।

अगली पंक्ति में n स्पेस-सेपरेटेड पूर्णांक होते हैं (1 ≤ ≤ )।

आउटपुट

कार्यक्रम को वह अधिकतम योग प्रिंट करना चाहिए जो आप एकत्रित कर सकते हैं।

उदाहरण

व्याख्या

1. आप सबसे पहले 3 उठाते हैं → 2 10 4

2. कंप्यूटर सबसे बड़ा तत्व (अंत वाला 4) उठाता है → 2 10

3. आप 10 उठाते हैं → 2

4. कंप्यूटर 2 उठाता है ⇒ आपने कुल 3 + 10 = 13 इकट्ठा किए।