{"problem":{"name":"Median of Medians","description":{"content":"We will define the **median** of a sequence $b$ of length $M$, as follows: *   Let $b'$ be the sequence obtained by sorting $b$ in non-decreasing order. Then, the value of the $(M / 2 + 1)$\\-th eleme","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc101_b"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^5$\n*   $a_i$ is an integer.\n*   $1 \\leq a_i \\leq 10^9$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$a_1$ $a_2$ $...$ $a_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc101_b","tags":[],"sample_group":[["3\n10 30 20","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$."],["1\n10","10"],["10\n5 9 5 9 8 9 3 5 4 3","8"]],"created_at":"2026-03-03 11:01:13"}}