{"raw_statement":[{"iden":"problem statement","content":"We have $N$ cards. The $i$\\-th card $(1 \\leq i \\leq N)$ has an integer $A_i$ written on it.\nTakahashi will choose any number of cards from these. However, for each $i$ $(1 \\leq i \\leq N - 1)$, at least one of the $i$\\-th and $(i+1)$\\-th cards must be chosen.\nFind the following values.\n\n*   The maximum possible average of the integers written on the chosen cards\n*   The maximum possible median of the integers written on the chosen cards\n\nHere, the median of the $n$ integers is defined to be the $\\lceil \\frac{n}{2} \\rceil$\\-th smallest of them, where $\\lceil x \\rceil$ is the smallest integer not less than $x$."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 10^5$\n*   $1 \\leq A_i \\leq 10^{9}$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $\\ldots$ $A_N$"},{"iden":"sample input 1","content":"6\n2 1 2 1 1 10"},{"iden":"sample output 1","content":"4\n2\n\nChoosing the $2$\\-nd, $4$\\-th, and $6$\\-th cards makes the average of the written integers $\\frac{12}{3} = 4$, which is the maximum possible.\nChoosing the $1$\\-st, $3$\\-rd, $5$\\-th, and $6$\\-th cards makes the median of the written integers $2$, which is the maximum possible."},{"iden":"sample input 2","content":"7\n3 1 4 1 5 9 2"},{"iden":"sample output 2","content":"5.250000000\n4\n\nFor the average, your output may contain some degree of error: for example, the output $5.2491$ is still considered correct. For the median, however, the exact value must be printed."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}