{"raw_statement":[{"iden":"problem statement","content":"We will define the **median** of a sequence $b$ of length $M$, as follows:\n\n*   Let $b'$ be the sequence obtained by sorting $b$ in non-decreasing order. Then, the value of the $(M / 2 + 1)$\\-th element of $b'$ is the median of $b$. Here, $/$ is integer division, rounding down.\n\nFor example, the median of $(10, 30, 20)$ is $20$; the median of $(10, 30, 20, 40)$ is $30$; the median of $(10, 10, 10, 20, 30)$ is $10$.\nSnuke comes up with the following problem.\nYou are given a sequence $a$ of length $N$. For each pair $(l, r)$ ($1 \\leq l \\leq r \\leq N$), let $m_{l, r}$ be the median of the contiguous subsequence $(a_l, a_{l + 1}, ..., a_r)$ of $a$. We will list $m_{l, r}$ for all pairs $(l, r)$ to create a new sequence $m$. Find the median of $m$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10^5$\n*   $a_i$ is an integer.\n*   $1 \\leq a_i \\leq 10^9$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$a_1$ $a_2$ $...$ $a_N$"},{"iden":"sample input 1","content":"3\n10 30 20"},{"iden":"sample output 1","content":"30\n\nThe median of each contiguous subsequence of $a$ is as follows:\n\n*   The median of $(10)$ is $10$.\n*   The median of $(30)$ is $30$.\n*   The median of $(20)$ is $20$.\n*   The median of $(10, 30)$ is $30$.\n*   The median of $(30, 20)$ is $30$.\n*   The median of $(10, 30, 20)$ is $20$.\n\nThus, $m = (10, 30, 20, 30, 30, 20)$ and the median of $m$ is $30$."},{"iden":"sample input 2","content":"1\n10"},{"iden":"sample output 2","content":"10"},{"iden":"sample input 3","content":"10\n5 9 5 9 8 9 3 5 4 3"},{"iden":"sample output 3","content":"8"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}