AT_pakencamp_2024_day1_e Goats

数直線上に $ 1,2, \ldots, N $ と番号がついた $ N $ 匹のヤギがいます。ヤギ $ i $ ははじめ座標 $ A_i $ にいます。ここで、ヤギははじめ相異なる座標にいることが保証されます。 以下の $ Q $ 個のクエリを $ i=1,2,\ldots,Q $ の順に処理してください。 座標 $ B_i $ に先生がエサを置き、エサからの距離が最も小さいヤギがエサを食べます。ただし、そのようなヤギが複数いる場合は、そのようなヤギの中で番号が最も小さいヤギがエサを食べます。また、座標 $ X $ と座標 $ Y $ の距離は $ \lvert X-Y \rvert $ であるとします。 それぞれのエサを食べるヤギの番号を求めてください。ただし、エサを食べたヤギはエサのある座標に移動し、そのままそこに残るものとします。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ Q $ $ B_1 $ $ B_2 $ $ \ldots $ $ B_Q $

各クエリに対して $ 1 $ 行で答えを出力せよ。

### Sample Explanation 1 $ 1 $ つ目のクエリでは、エサが置かれる $ 11 $ に最も近い $ 10 $ にいるヤギ $ 1 $ がエサを食べ、 $ 11 $ に移動します。 $ 2 $ つめのクエリでは、エサが置かれる $ 9 $ に近いヤギは $ 7 $ にいるヤギ $ 2 $ と $ 11 $ にいるヤギ $ 1 $ がいます。そのため、より番号の小さいヤギ $ 1 $ がエサを食べ、 $ 9 $ に移動します。 ### Constraints - $ 1 \leq N,Q \leq 2 \times 10^5 $ - $ -10^{18} \leq A_i \leq 10^{18} $ ( $ 1 \leq i \leq N $ ) - $ A_i \neq A_j $ ( $ 1 \leq i < j \leq N $ ) - $ -10^{18} \leq B_i \leq 10^{18} $ ( $ 1 \leq i \leq Q $ ) - 入力は全て整数