bzoj#P2653. middle
middle
题目描述
一个长度为 的序列 ,设其排过序之后为 ,其中位数定义为 ,其中 从 开始标号,除法取下整。
给你一个长度为 的序列 。
回答 个这样的询问: 的左端点在 之间,右端点在 之间的子区间中,最大的中位数。
其中 。位置也从 开始标号。
我会使用一些方式强制你在线。
输入格式
第一行序列长度 。
接下来 行按顺序给出 中的数。
接下来一行 。
然后 行每行 ,我们令上个询问的答案是 (如果这是第一个询问则 )。
令数组 $q=\{(a+x)\bmod n,(b+x)\bmod n,(c+x)\bmod n,(d+x)\bmod n\}$。
将 从小到大排序之后,令真正的要询问的 。
输入保证满足条件。
输出格式
行依次给出询问的答案。
样例
5
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4 0
271451044
271451044
969056313
数据范围与约定
对于 的数据, 。
对于另 的数据, 。
对于 的数据, ,。