Old and Cold Numbers
Tag(s):

## Basic Programming, Basics of Implementation, Easy, Implementation, hiring, observation

Problem
Editorial
Analytics

Let's define Old number as a number $X$, such that it is divisible by count of odd integers in the range $1$ to $X$. If number does not hold this property, then such number is defined as Cold number.
You are given an array $A$ and $Q$ tasks of the form $L$ $R$, you have to find what is the minimum numbers of steps needed to make subarray from $L$ to $R$ balanced.
Any subarray is said to be balanced if count of Old number(s) is not less than count of Cold number(s) in that subarray. In every step, you can either increase the value of some array element by 1 or you can decrease an array element by 1.

Note: All tasks are independent of each other.

Input Format:
First line contains an integer $T$, denoting the number of testcases.

In each test case:
Firstl line contains $N$, the number of elements in array $A$.
Next line contains $N$ space separated integers denoting array elements.
Next line contains $Q$, the number of queries.
Each of the next $Q$ lines contains two space separated integers $L$ and $R$.

Output Fomat:
For each task, print total number of steps needed to change the subarray such that subarray from $L$ to $R$ is balanced.
Answer for each task should be printed in a new line.

Constraints:
$1 \le T \le 2$
$1 \le N,Q \le 5 * 10^4$
$1 \le A_i \le 10^9$
$1 \le L \le R \le N$

SAMPLE INPUT
1
7
9 2 10 7 11 8 11
3
1 7
1 6
4 6

SAMPLE OUTPUT
1
0
1

Explanation

In first case, there are 3 numbers from 1 to 7 which are Old numbers that are 2,8,and 10.If last number 11 is decreased by 1 step to 10, then there will be total 4 numbers out of 7 which are Old numbers.

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), 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, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...
Your Rating:

## This Problem was Asked in

Challenge Name

Capillary Software Developer Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Greedy Algorithms
• Algorithms > Dynamic Programming
Notifications

?