Can you answer these queries ??

0

0 votes
Problem

Well..you have quite a good knowledge about segment tress... well lets test it.. you are given an array of integers Ai ,you need to calculate a function foo... defined as... sum of elements from L to R ,[L,R] ,(inclusive) - maximum element from [L,R]

you will be given Q queries . you need to find function foo query will include 2 intergers ,L and R , 1<=L<=R<=N

constraints are 1<=L<=R<=N 1<=N<=100000 1<=Q<=100000 sum will not exceed 10^9

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

for first query 1 1 , sum is 1 and max is 1 .. so , answer is 0

Editor Image

?