We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home
  • |
  • Prepare
  • Certify
  • Compete
  • Apply
  • Hiring developers?
  1. Prepare
  2. Functional Programming
  3. Functional Structures
  4. Stock Prediction

Stock Prediction

Problem
Submissions
Leaderboard
Discussions
Editorial

George is very concerned about the stock options his company has granted him, because the company's stock price has fluctuated unpredictably and has often failed to meet expectations. With this in mind, George has decided to sell his options. Before doing so, he would like to perform a series of calculations.

Stock price history is presented as an array of positive integers, , which represents the average price per day of that stock. For a given day and margin , George needs to find the longest subarray containing the day's entry as a minimum, , and all other entries not exceeding .

That is, he has to find the longest subarray, , such that

George asks you to help him solve this problem.

Input Format

The first list contains an integer which represents the length of the array . The second line contains space-separated integers, , which represent the element of array . The next line contains the number of queries . Each of the subsequent lines contain two integers and which represent the index of the element, which should be minimal and be included in subarray, and margin, respectively.

Output Format

For each query output the length of the longest subarray with the required properties.

Constraints




Sample Input

5
3 5 2 6 1
2
0 2
2 3

Sample Output

2
3

Explanation

Query #1: The first element, , should be included in the subarray. Since is not less than and does not cross the margin (), it can be included. The third element, , is less than the first element, so it cannot be included. To that end, the answer here is 2, as the longest subarray will be .

Query #2: Here and . The next element, , is excluded because it is greater than the margin, . All of the previous elements will be included, as they are within the allowed range . To that end, the longest subarray will be and have a length of 3.


Tested by Bo You

Author

pakso

Difficulty

Hard

Max Score

80

Submitted By

614

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Helpdesk
  • Careers
  • Terms Of Service
  • Privacy Policy

Cookie support is required to access HackerRank

Seems like cookies are disabled on this browser, please enable them to open this website