Peak Count
Tag(s):

## Easy, dp

Problem
Editorial
Analytics

Given sequence A,A,..... ,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, A , .... , 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

SAMPLE INPUT
10 5
4 2 7 9 6 4 3 7 2 1
1 10
3 4
2 8
6 7
8 10
SAMPLE OUTPUT
3
1
2
0
1
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), TypeScript, Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

Codester Novice Prelims

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Stacks