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
for first query 1 1 , sum is 1 and max is 1 .. so , answer is 0