Find the Duplicate and Missing Number in an Array

You are given an array of n integers where the integers are supposed to be all the numbers from 1 to n exactly once. However, one of the numbers appears twice and consequently, another number is missing.

Your task is to find the duplicate number and the missing number. Formally, let the array be \(a_1, a_2, \ldots, a_n\) and it should have contained all the integers from \(1\) to \(n\). Instead, one number \(d\) appears twice and one number \(m\) is absent. You must determine \(d\) and \(m\).

Input/Output: The program reads from standard input (stdin) and writes to standard output (stdout).

inputFormat

The first line contains a single integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers, representing the array elements. It is guaranteed that the array contains exactly one duplicate number and one missing number from the range \(1\) to \(n\).

outputFormat

Print two space-separated integers: first, the duplicate number, and second, the missing number.

6
4 3 6 2 1 1

1 5