School prayer
Practice
0 (0 votes)
Medium
Sorting
Algorithms
Advanced sorting
Arrays
Set
Advanced sorting
Problem
77% Success 63 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

You are given the task to manage students coming to morning prayer in the school. The students whose roll numbers lie between \(1\) to \(N\) are coming in an arbitrary manner. You are required to make these students stand in a queue such that queue is always in ascending order of roll numbers.

For every incoming student, you must find a student in the queue he will be standing behind (or in front of the queue if no such student is present in the queue). For example, if the queue is \(1\ 2\ 4\) and student with roll number \(3\) arrives, you must locate \(2\) and make \(3\) stand behind \(2\).
For each incoming student, determine the roll number of the student he or she will be standing behind. Print \(-1\) in case no student with the roll number less than the current roll number exists.

Input format

  • First line: \(T\) denoting the number of test cases
  • For each test case:
    • First line: \(N\) denoting the number of students
    • Second line: \(N\) distinct space-separated numbers denoting the order in which each student is coming

Output format
Print a single number that represents the sum of \(N\) numbers where the \(i^{th}\) number denotes the answer for the \(i^{th}\) incoming student. The answer for each test case must come in a new line.

Constraints
\(1 \le T \le 10\)
\(1 \le N \le 10^{5}\)
\(1 \le Roll \; Number \le N\)

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:20
48 votes
Tags:
Data StructuresEasyHash MapsPriority queueQueue
Points:20
Tags:
Basic ProgrammingEasy
Points:30
Tags:
OpenOpenOpenMath BasicBasic MathEasyMathematicsMath