Mrityunjay is a high-school teacher, currently coaching students for JEE (Joint Entrance…
- User
Mrityunjay is a high-school teacher, currently coaching students for JEE (Joint Entrance Exam). Mrityunjay every year gives prizes to the toppers of JEE in India. A lot of students give this exam in India and it is difficult for him to manually go through results and select two top students from them. So he asked for your help. He is interested in knowing the scores of top two students in the exam. You are given scores of all the students appeared for this exam. Now tell him the scores of two toppers. Remember that top two scores may be the same. Input Description
The first line contain N, the number of students appeared for JEE. Next line contains N integers, scores of all the students.
Output Description Output in a single line two space separated integers, highest sore and second highest score.
Constraints 2 ≤ N ≤ 2 * 10^5, 1 ≤ Ai ≤ 10^9
Example
Input
3 12 20 12
Output
20 12
Input
3 30 30 20
Output
30 30
Explanation: In the given case top two scores are 20 and 12. In sample example 2 , like we have "Clearly" mentioned, two toppers may have same score i.e. highest score = 30 , second highest score = 30.
Assistant
We need to write solution for a problem: given N and list of scores, find highest and second highest. Constraints up to 2e5, so O(N) fine.
We read integer N, then list of N integers. Output max and second max.
Edge cases: N >=2, so there is at least two scores. If scores are all equal, both max and second max are same.
Implementation: read input, compute max1 and max2. Use Python.
But the conversation: user asked to "write a solution" for the problem. They want code. I should output final answer with code.
But they also gave description and examples. I'll write a Python solution: read input via sys.stdin, parse ints, compute.
Potential pitfalls: large input, so use sys.stdin.read().split().
Implementation:
def main(): import sys data = sys.stdin.read().split() if not data: return n = int(data[0]) scores = list(map(int, data[1:1+n])) max1 = -1 max2 = -1 for s in scores: if s > max1: max2 = max1 max1 = s elif s > max2 and s != max1: max2 = s elif s == max1: # max1 remains, but we need to allow duplicate for second max? Actually if duplicates, we need second max to be same as max if there are at least two occurrences. In our update, if s == max1, we could treat as need to set max2 = max1 if max2 < max1? But careful: we want top two scores, so if there are multiple occurrences of the max, then both top two are that max. So we should set max2 = max1 if max2 < max1? Actually we need to allow second max to be same as first if count>=2. So we need to handle that. # Current logic: when s == max1, we skip. But max2 remains less. So we should treat it as: if s == max1 and max2 < max1: then we can set max2 = s? But careful: if we have [30,20], max1=30, max2=20. That's correct. If we have [30,30,20], after first 30: max1=30, max2=-1; second 30: s == max1, we could set max2=30 if max2 < max1. So we need to check: if s == max1 and max2 < max1: then max2 = s. But also if we have [30,30,30], after first: max1=30, max2=-1; second: s==max1, max2<max1 so set max2=30; third: s==max1, but max2 == max1, so no change (but that's fine, second max is still 30). # Alternatively, we can just sort unique? But O(N log N) okay but N up to 2e5, sorting is O(N log N) which is fine but we can do linear. # Let's implement correctly. pass # but my above update in loop doesn't include duplication. So I'll add condition: # Typically approach: initialize with -inf. For each s: # if s > max1: max2 = max1; max1 = s # elif s > max2: max2 = s # That's it? If s == max1, it's not > max1, and it's not > max2 unless max2 < s. For [30,30,20], after first: max1=30, max2=-inf; second: s=30, s > max2? Yes, -inf < 30, so max2 becomes 30. That works! Because we use elif s > max2, not elif s >= max2. So we need to use >, not >=, to avoid making max2 equal to max1 when there is only one occurrence? But we want to allow duplicate max to set max2 to max1. In second iteration, s=30 > max2? Since max2 = -inf, yes, so max2=30. That's correct. After that, for third s=20: s > max1? no; s > max2? 20 > 30? no. So max2 stays 30. Good. So simple approach works if we initialize max2 to a very low number (like -1 or -inf). But careful: if scores can be 0? Actually scores are >=1, so -1 works as sentinel. However if we have max1=10, max2=-1, and s=10: s > max1? false; s > max2? 10 > -1 true, so max2 becomes 10. So duplicate sets second max. Good. So we can just do: # if s > max1: max2 = max1; max1 = s # elif s > max2: max2 = s # That's it. But need to ensure we don't accidentally set max2 to max1 when there is only one max? Actually the first duplicate will set max2 to max1, which is correct because second highest is also max1 (if there are at least two max). So it's fine. # But what about scenario: [30,20,20]: after first: max1=30, max2=-1; second: s=20, s > max1? no; s > max2? 20 > -1 yes => max2=20; third: s=20, s > max1? no; s > max2? 20 > 20? false, so no change. So correct. # So we don't need special handling.
But careful: initial values: max1 = -1, max2 = -1. If all scores are >=1, this works. However, if we have scores where max1 = 1 and max2 = -1, but we need second highest maybe also 1? Actually if only one occurrence of 1 and others lower? That's fine because max2 will be set to something else. But if we have only two numbers: [1,2]? Process: start max1=-1, max2=-1. s=1: 1 > -1 => max2 = -1, max1=1. s=2: 2 > 1 => max2 = 1, max1=2. So output 2 1. correct. If [2,2]: s=2 first: max1=2, max2=-1; second s=2: not > max1, but > max2? 2 > -1 => max2=2. Output 2 2. Good.
So simple approach works.
But wait: if N=2 and scores [5,5] => output 5 5. works.
If N=3 and scores [5,5,5] => after first: max1=5, max2=-1; second: 5 > -1 => max2=5; third: 5 > max2? false, so max2=5. Output 5 5. Works.
Thus final solution: read, compute, print.
Complexities: O(N) time, O(1) extra.
Write code:
import sys
def main(): data = sys.stdin.read().split() if not data: return n = int(data[0]) # It's possible that there are more numbers? but we'll only take first n after n. scores = list(map(int, data[1:1+n])) max1 = -1 max2 = -1 for s in scores: if s > max1: max2 = max1 max1 = s elif s > max2: max2 = s # According to problem, N >= 2, so max2 will be set at least some value (maybe same as max1) # But just in case, if N=1? Not allowed by constraints. sys.stdout.write(f"{max1} {max2}")
if name == "main": main()
That solves.
But the user might want explanation? The instruction: "write a solution". Usually we provide code in final answer. So final answer: Python code.
I'll output the code. ```python
import sys
def main(): data = sys.stdin.read().split() if not data: return n = int(data[0]) scores = list(map(int, data[1:1 + n]))
max1 = -1 # highest score max2 = -1 # second highest score for s in scores: if s > max1: max2 = max1 max1 = s elif s > max2: max2 = s sys.stdout.write(f"{max1} {max2}")if name == "main": main()