P17533 [JAG 2026 Summer Camp #1] Longest Symmetry

There are $N$ houses numbered $1,2,\ldots,N$ on a number line. House $i$ is located at coordinate $X_i$. It is guaranteed that $X_i

The input consists of a single test case of the following format: ```text N X_1 X_2 ... X_N Q l_1 r_1 l_2 r_2 ... l_Q r_Q ``` The first line contains an integer $N$, representing the number of houses ($2\le N\le 2\times 10^5$). The second line contains $N$ integers $X_1,X_2,\ldots,X_N$, representing the coordinates of the houses ($-10^9\le X_i\le 10^9$). It is guaranteed that $X_i

For each query, output the maximum possible width.