This question is not from Cf or somewhere else. If you found any questions that match it by coincidence, it would be really helpful if you shared them.

I was trying to make a question mixed with pre-computing and gcd. Brute Force may be applied. But I cannot find another way to solve the bigger constraints. Help needed.

Time limit per test: 2 seconds 
memory limit per test: 265 megabytes 

Anish found a magical number in the dark forest. Becoming greedy, he made a lot of numbers with it.

let the magical number be x .

You are given an array that Anish made. Where the i th number is

ai = x * n ; where n is an arbitrary integer ( possibly 0 )

Now, print the maximum possible number Anish could have found. and,

You will be given q queries. Each query consists of 2 indices, i and j. For each query, print the maximum number required to make the numbers within the interval [i, j] in that array.

Input:

The first line contains a single integer t, the number of test cases. (1 <= t <= 1000)

Each test case consists of:

1. An integer n — size of the array (1 <= n <= 100,000)

1. n integers a1, a2, …, an (1 <= ai <= 10^9)

1. An integer q — number of queries (1 <= q <= 100,000)

1. q lines, each containing two integers i and j . (1 <= i <= j <= n)

Sum of all n over all test cases ≤ 2×10^5

Sum of all q over all test cases ≤ 2×10^5.

Output:

For each test case:

1. Print a single integer: maximum possible number Anish could have found . (for the whole array)

1. Next q lines: for each query, print the maximum possible number to make the numbers in that subarray [i, j]

Example:

Input:

1
4
7 15 30 39
3
2 3
2 4
1 3

Output:

1
15
3
1

Hi,

While trying to find a good resource to learn about the topics of CP, I came across many sites and PDFs. The most attractive thing (personally) I found was the CodeChef. https://www.codechef.com/roadmap/become-5-star

But this was premium, so I had to move on, as I am doing CP just out of passion. The next good resource I found was a blog on GeekForGeeks. https://www.geeksforgeeks.org/dsa/competitive-programming-a-complete-guide/

I am still learning, so I can't give a proper review. But what I like about it is that it includes a lot of content and a good number of exercises. So, I thought to share this with anyone like me who just got started with CP.

And one last thing, I would recommend that it's good to know the basics first, so you might not struggle with understanding the concepts in the blog.

If you also have a good resource, it would be really appreciated if you shared it.

Thanks