Given sequence A[1],A[2],..... ,A[n], A[i] is called a peak if A[i] is greater than it's adjacent elements. Given an array of N integers & Q queries, determine the number of peaks in range [L,R] for each query.

Indexing is 1 based.

Input :

First line contains a two integers N,Q - number of integers and number of queries

Next line consists of N integers, A[1], A[2] , .... , A[n]

Next Q lines contain two integers L and R respectively.

Output :

For each query , output a single integer - number of peaks in [L,R] , in a separate line.

Constraints :

2 <= N <= 1000000

1 <= Q <= 100000

1 <= A[i] <= 1000000000