All Tracks Data Structures Disjoint Data Structures Basics of Disjoint Data Structures Problem

Group Range
/

Data Structures, Disjoint Data Structures, Disjoint Set, Disjoint set, Implementation

Problem
Editorial
Analytics

You are given \(N\) integers. You are required to perform \(Q\) queries. In each query, you are given two integers \(x\) and \(y\). Your task is to merge the groups that contain the \(x^{th}\) and \(y^{th}\) integer to a single group. After performing each query, you are required to print the range of numbers that lie in the newly-formed group. Initially, the numbers do not belong to any group. 

Input format

  • First line: \(N\) denoting the number of integers
  • Next line: \(N\) space-separated integers denoting \(N\) integers
  • Next line: \(Q\) denoting the number of queries
  • Next \(Q\) lines: Integers \(x\) and \(y\)

Output format

For every query, print two space-separated integers \(min\) and \(max\) in a new line, where \(min\) is the minimum element and \(max\) is the maximum element of the new group formed.

Constraints

\(1 \leq N, Q \leq 2 * 10^5\)

\(-10^{18} \leq integer_{i} \leq 10^{18}\)

\(1 \leq x, y \leq N\)

SAMPLE INPUT
5
5 8 12 6 1
3
1 3
2 4
5 5
SAMPLE OUTPUT
5 12
6 8
1 1
Explanation

Query 1: The group now contans {5, 12}

Query 2: The group now contans {6, 8}

Query 3: The group now contans {1}

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?