#P1053. HDSF大学保研机试-2022-Minimum_Sum

HDSF大学保研机试-2022-Minimum_Sum

题面

你有一个序列a1,a2,...,ana_1,a_2,...,a_n,然后给你一些区间[l,r][l,r].对于每一个区间,你需要找到下式的最小值,对于所有可能的xx

∑i=lr∣x−ai∣\sum_{i=l}^{r}|x-a_i|

输入格式

第一行一个整数N(N≤105)N(N \leq 10^5) 代表序列长度。

接下来一行有NN个正整数ai(1≤ai≤109)a_i(1 \leq a_i \leq 10^9),用空格隔开。

接下来一行一个整数Q(1≤Q≤105)Q(1 \leq Q \leq 10^5),代表询问的区间次数。

接下来QQ行，每行一个区间l,r(1≤l≤r≤N)l,r(1 \leq l \leq r \leq N)

输出格式

输出QQ行。每行代表对应的区间的结果。

样例

input

5
2 3 3 4 4
3
1 2
2 2
2 5

output

1
0
2

知识点:*****

查看知识点以及同类型题目

Statistics

  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 湘ICP备2023007293号
  3. Worker 0, 37ms
  4. Powered by Hydro v4.11.1 Community