{"raw_statement":[{"iden":"statement","content":"I was tired. Tired of hiding and wandering. Throw the rules out the window, odds are you'll go that way too. I just wanted everything to be finished. The crying heavens had already given a verdict for me, I was just looking for somebody to execute it. The castle of Dragon was not defenseless, it was ready for my visit. The beast inside me was woking up and rubbing his eyes.\n\nI had already known every single bandit guarding Dragon's castle. It was quite useful to have connections in knight orders. There were only n men there. There had been some bigger frays. And not all of them desperately wanted to die by my hand that night. I knew that the i-th of them would have decided to fight only if at least ai other bandits had decided the same. I was slowly approaching the gates, wondering what was the maximal number of people who might have opposed me.\n\nThe first line contains a single integer n (1 ≤ n ≤ 105) — the number of bandits in the castle of Dragon.\n\nThe second line contains n integers separated by spaces: ai (0 ≤ ai ≤ 109) — the minimal number of other bandits with whom together the i-th bandit is ready to fight.\n\nOutput a single integer — the maximal number of bandits that might be ready to fight for Dragon's castle.\n\n"},{"iden":"input","content":"The first line contains a single integer n (1 ≤ n ≤ 105) — the number of bandits in the castle of Dragon.The second line contains n integers separated by spaces: ai (0 ≤ ai ≤ 109) — the minimal number of other bandits with whom together the i-th bandit is ready to fight."},{"iden":"output","content":"Output a single integer — the maximal number of bandits that might be ready to fight for Dragon's castle."},{"iden":"examples","content":"Input64 2 1 6 0 3Output5Input61 3 6 1 3 5Output4"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ M_k: \\Sigma \\times \\Sigma \\to \\Sigma $ be a symmetric binary operation over $ \\Sigma = \\{a, b, \\dots, z\\} $, represented by a $ 26 \\times 26 $ matrix where $ M_k[i][j] $ is the result of combining the $ i $-th and $ j $-th lowercase letters (with $ a = 1, \\dots, z = 26 $), and $ M_k[i][j] = M_k[j][i] $.  \n- Let $ A_k = (a_1, a_2, \\dots, a_n) \\in \\Sigma^n $ be the input string of length $ n = |A_k| $, with $ 1 \\leq n \\leq 10{,}000 $.  \n- Let $ V = \\{a, e, i, o, u\\} \\subset \\Sigma $ be the set of vowels.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq \\text{some bound (unspecified)} $  \n2. For each $ k $:  \n   - $ M_k $ is symmetric: $ M_k[i][j] = M_k[j][i] $ for all $ i,j \\in \\{1,\\dots,26\\} $  \n   - $ 1 \\leq |A_k| \\leq 10{,}000 $  \n\n**Game Rules**  \n- Two moves:  \n  - **LEFT**: Replace the two rightmost characters $ (a_{n-1}, a_n) $ with $ M_k(a_{n-1}, a_n) $, reducing string length by 1.  \n  - **RIGHT**: Replace the two leftmost characters $ (a_1, a_2) $ with $ M_k(a_1, a_2) $, reducing string length by 1.  \n- Players alternate turns, Salah starts first.  \n- Game ends when string has length 1.  \n- Salah wins if the final character $ \\in V $; otherwise Marzo wins.  \n- Both players play optimally.  \n\n**Objective**  \nFor each test case $ k $, determine the winner under optimal play:  \n$$\n\\text{Winner}(k) = \n\\begin{cases}\n\\text{Salah} & \\text{if the final character under optimal play} \\in V \\\\\n\\text{Marzo} & \\text{otherwise}\n\\end{cases}\n$$","simple_statement":"Salah and Marzo play a game on a string of lowercase letters. They have a 26x26 table that defines how any two letters combine into one new letter.  \n\nOn each turn:  \n- **LEFT**: Combine the string from right to left — take the last two letters, replace them with their combined letter, and repeat until one letter remains.  \n- **RIGHT**: Combine the string from left to right — take the first two letters, replace them with their combined letter, and repeat until one letter remains.  \n\nSalah goes first. Players alternate turns, choosing either LEFT or RIGHT move. The game ends when only one letter remains.  \n\nSalah wins if the final letter is a vowel (**a, e, i, o, u**). Marzo wins otherwise.  \n\nBoth play optimally. Given the combination table and the initial string, determine the winner.","has_page_source":false}