跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F1946. Function

  • ID: 1952
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:挑战
  • 上传者:
  • 数据结构
  • 挑战
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Function

题目描述

E. Function
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Serega and Fedor play with functions. One day they came across a very interesting function. It looks like that:

  • f(1,j)=a[j], 1≤j≤n.
  • f(i,j)=min(f(i-1,j),f(i-1,j-1))+a[j], 2≤i≤n, i≤j≤n.

Here a is an integer array of length n.

Serega and Fedya want to know what values this function takes at some points. But they don't want to calculate the values manually. So they ask you to help them.

Input

The first line contains integer n (1≤n≤105) − the length of array a. The next line contains n integers: a[1],a[2],...,a[n] (0≤a[i]≤104).

The next line contains integer m (1≤m≤105) − the number of queries. Each of the next m lines contains two integers: xi, yi (1≤xi≤yi≤n). Each line means that Fedor and Serega want to know the value of f(xi,yi).

Output

Print m lines − the answers to the guys' queries.

Examples
Input
6
2 2 3 4 3 4
4
4 5
3 4
3 4
2 3
Output
12
9
9
5
Input
7
1 3 2 3 4 0 2
4
4 5
2 3
1 4
4 6
Output
11
4
3
0

题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 1526 题。保留原作者与原赛事署名。