All Tracks Problem

Peak Count
Tag(s):

Easy, dp

Problem
Editorial
Analytics

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

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...
Your Rating:

Contributor

This Problem was Asked in

University School of Information and Communication Technology, Guru Gobind Singh Indrapratha University, Delhi

Challenge Name

Codester Novice Prelims

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?