A. Prefix range (C language)

One 、 subject

Garlic Junyou nnn Number , He put forward qqq A question , Each question is to say , Before asking xxx The range of numbers （ Maximum minus minimum ）. You can help him solve this qqq A question ？

Input

The first line has two integers n,q(1≤n,q≤105)n, q(1 \leq n, q \leq 10 ^ 5)n,q(1≤n,q≤105)

The second line nnn It's an integer ai(1≤ai≤109)a_i(1 \leq a_i \leq 10 ^ 9)ai​(1≤ai​≤109)
It means Mr. garlic nnn Number

The third line qqq It's an integer xi(1≤xi≤n)x_i(1 \leq x_i \leq n)xi​(1≤xi​≤n) , Means every time you ask

Output

Output one line , contain qqq It's an integer , Indicates the answer to each question

Sample 1
Inputcopy Outputcopy

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

	

0 1 2 3 4

Two 、 Solution

1. Ideas

① This question is based on its meaning , We have to calculate first x Range of items , Then we need to know before x The maximum and minimum values of the item , In the code written before , I am here for Before each calculation in the cycle x Range of items , The final result is a timeout .
② So to simplify our code , When we re-enter the number, we put it before it x The maximum and minimum values of the term are calculated , You can use it directly in the back , It avoids repeated operations

——————————————

2. Code

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
    
	int n=0,q=0;
	scanf("%d %d",&n,&q);
	int arr[100005]={
    0};
	int max[100005]={
    0},min[100005]={
    0};
	for(int i=1;i<=n;i++)
	{
    
		scanf("%d",&arr[i]);
		if(i==1)
		{
    
			max[i]=arr[i],min[i]=arr[i];
		}
		else
		{
    
			max[i] = max[i-1]>arr[i]?max[i-1]:arr[i];
			min[i] = min[i-1]<arr[i]?min[i-1]:arr[i];
		}
	} 
	int x=0;
	for(int i=0;i<q;i++)
	{
    
		scanf("%d",&x);
		printf("%d ",max[x]-min[x]);
	}
	return 0;
}