{"problem":{"name":"Average and Median","description":{"content":"We have $N$ cards. The $i$\\-th card $(1 \\leq i \\leq N)$ has an integer $A_i$ written on it. Takahashi will choose any number of cards from these. However, for each $i$ $(1 \\leq i \\leq N - 1)$, at leas","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc236_e"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 10^5$\n*   $1 \\leq A_i \\leq 10^{9}$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_1$ $\\ldots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc236_e","tags":[],"sample_group":[["6\n2 1 2 1 1 10","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."],["7\n3 1 4 1 5 9 2","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."]],"created_at":"2026-03-03 11:01:14"}}