Arranha-Céus da Nlogonia

Recentemente, com o aumento drástico de níveis do ar, o prefeito da Nlogonia está preocupado com os $n$ arranha-céus da cidade. Esses imensos prédios estão todos em uma avenida beira-mar, e portanto correm sério perigo. A cada dia, o nível do mar cresce por exatamente um metro, e cada prédio tem $A_i$ metros de altura. Consideraremos um $quarteirao$ de arranha-céus como uma sequência contígua de arranha-céus adjacentes tal que todas as alturas desses arranha-céus sejam estritamente maiores que o nível do mar atual. O prefeito da Nlogonia quer saber, em $q$ dias diferentes, quantos quarteirões ainda existem na cidade.

Entrada:

A primeira linha de entrada contém um inteiro $t$ , o número de casos de teste. Seguem então $t$ casos de teste

A primeira linha de cada caso de teste contém dois inteiros: $n$ e $q$ .
A segunda linha de cada caso de teste descreve os arranha-céus, em ordem, ou seja o $i$ -ésimo arranha céu é adjacente ao $i-1$ ésimo arranha-céu, se existir, e ao $i+1$ -ésimo arranha-céu, se existir. Essa linha contém $n$ inteiros, onde o $i$ -ésimo inteiro indica $A_i$ .

A terceira linha de cada caso indica os dias que o prefeito quer saber quantos quarteirões ainda existem, tendo $q$ inteiros $d_i$ , dados em ordem estritamente crescente.

Saída

A saída deve conter $q$ inteiros, para cada caso de teste, onde o $i$ -ésimo inteiro deve conter o número de quarteirões no dia $d_i$ .

Restriçoes:

$1 \leq t \leq 15$
$1 \leq n, q, \leq 10^6$
$1 \leq A_i \leq 10^9$
$0 \leq d_i \leq 10^9$

Exemplos:

Entrada	Saida
2 3 3 1 2 3 1 2 3 5 3 1 3 5 1 3 0 2 4	1 1 0 1 2 1

NOTA: use as seguintes funções para leitura e impressão em C++:

Leitura:

	void getint(int &x){
	register int c = getchar_unlocked();
	x = 0;
	for(;(c<48 \|\| c>57);c = getchar_unlocked());
	for(;c>47 && c<58;c = getchar_unlocked()) {x = (x<<1) + (x<<3) + c - 48;}
	}

view raw

getintreal.cpp

hosted with ❤ by GitHub

Saída:

	inline void print(int n){
	if (n == 0)
	{
	putchar_unlocked('0');
	putchar_unlocked('\n');
	}
	else if (n == -1)
	{
	putchar_unlocked('-');
	putchar_unlocked('1');
	putchar_unlocked('\n');
	}
	else
	{
	char buf[11];
	buf[10] = ' ';
	int i = 9;
	while (n)
	{
	buf[i--] = n % 10 + '0';
	n /= 10;
	}
	while (buf[i] != ' ')
	putchar_unlocked(buf[++i]);
	}
	}

view raw

print.cpp

hosted with ❤ by GitHub

Para submeter sua solução use esse link.