{"id":"7cb94184-bea5-443c-ba45-a499bd4f4e29","name":"Square Root Decomposition","description":"You are given a list of N numbers and Q queries.Each query is specified by two numbers i and j.The answer to\r\neach query is the minimum number between the range between i and j(including i and j).The query are specified using 0 based indexing.\r\n\r\nExpected complexity : O(Q * logN)","inputFormat":"The first line contains N. The next line holds N numbers. Following the list is a number Q. The next Q lines each contain two numbers i and j which specify a query you must answer.","outputFormat":"For each query, output the Minimum in the range in a line.","constraints":"1<= N <= 10^6\r\n1 <= Q <= 10^5\r\n0 <= i,j <= N-1","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.BufferedReader;\r\nimport java.io.IOException;\r\nimport java.io.InputStreamReader;\r\nimport java.util.Arrays;\r\n\r\npublic class Main {\r\n\r\n\tpublic static void main(String[] args) throws NumberFormatException, IOException {\r\n\t\t\r\n\t}\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"4\r\n2 4 3 1\r\n4\r\n1 2\r\n1 3 \r\n2 2\r\n0 1","sampleOutput":"3\r\n1\r\n3\r\n2\r\n","questionVideo":"https://www.youtube.com/embed/K54R2D9bilQ","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"ed294401-c1be-4c10-a3f7-3e2e4f8d9755","name":"Range Queries For Experts","slug":"range-queries-for-experts-903","type":0},{"id":"8df650ba-ffc6-4622-b357-34779040e18e","name":"Square Root Decomposition","slug":"square-root-decomposition","type":1}],"next":{"id":"09980edb-846f-4c16-9720-812d81e5ed58","name":"Point Update In Square Root Decomposition","type":1,"slug":"point-update-in-square-root-decomposition"},"prev":{"id":"708eaf40-ad8a-4b4f-b9f6-8c4276e08d11","name":"Moksh And His Girlfriend","type":1,"slug":"moksh-and-his-girlfriend"}}}

Square Root Decomposition

You are given a list of N numbers and Q queries.Each query is specified by two numbers i and j.The answer to each query is the minimum number between the range between i and j(including i and j).The query are specified using 0 based indexing. Expected complexity : O(Q * logN)

{"id":"7cb94184-bea5-443c-ba45-a499bd4f4e29","name":"Square Root Decomposition","description":"You are given a list of N numbers and Q queries.Each query is specified by two numbers i and j.The answer to\r\neach query is the minimum number between the range between i and j(including i and j).The query are specified using 0 based indexing.\r\n\r\nExpected complexity : O(Q * logN)","inputFormat":"The first line contains N. The next line holds N numbers. Following the list is a number Q. The next Q lines each contain two numbers i and j which specify a query you must answer.","outputFormat":"For each query, output the Minimum in the range in a line.","constraints":"1<= N <= 10^6\r\n1 <= Q <= 10^5\r\n0 <= i,j <= N-1","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.BufferedReader;\r\nimport java.io.IOException;\r\nimport java.io.InputStreamReader;\r\nimport java.util.Arrays;\r\n\r\npublic class Main {\r\n\r\n\tpublic static void main(String[] args) throws NumberFormatException, IOException {\r\n\t\t\r\n\t}\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"4\r\n2 4 3 1\r\n4\r\n1 2\r\n1 3 \r\n2 2\r\n0 1","sampleOutput":"3\r\n1\r\n3\r\n2\r\n","questionVideo":"https://www.youtube.com/embed/K54R2D9bilQ","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"ed294401-c1be-4c10-a3f7-3e2e4f8d9755","name":"Range Queries For Experts","slug":"range-queries-for-experts-903","type":0},{"id":"8df650ba-ffc6-4622-b357-34779040e18e","name":"Square Root Decomposition","slug":"square-root-decomposition","type":1}],"next":{"id":"09980edb-846f-4c16-9720-812d81e5ed58","name":"Point Update In Square Root Decomposition","type":1,"slug":"point-update-in-square-root-decomposition"},"prev":{"id":"708eaf40-ad8a-4b4f-b9f6-8c4276e08d11","name":"Moksh And His Girlfriend","type":1,"slug":"moksh-and-his-girlfriend"}}}
plane

Editor

Loading...

Square Root Decomposition

hard

You are given a list of N numbers and Q queries.Each query is specified by two numbers i and j.The answer to each query is the minimum number between the range between i and j(including i and j).The query are specified using 0 based indexing. Expected complexity : O(Q * logN)

Constraints

1<= N <= 10^6 1 <= Q <= 10^5 0 <= i,j <= N-1

Format

Input

The first line contains N. The next line holds N numbers. Following the list is a number Q. The next Q lines each contain two numbers i and j which specify a query you must answer.

Output

For each query, output the Minimum in the range in a line.

Example

Sample Input

4 2 4 3 1 4 1 2 1 3 2 2 0 1

Sample Output

3 1 3 2

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode