D - Duplicated? Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

注意

この問題に対する言及は、2019年12月29日 05:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

長さ N の整数列がサーバーに保管されている。つい先ほどまで、この列には 1 から N までの整数が 1 個ずつ含まれていた。

しかし、たった今発生したトラブルにより、列のいずれか 1 個の要素が別の 1 以上 N 以下の整数に書き換えられた可能性がある。あるいは、何の書き換えも発生しなかったかもしれない。

トラブル発生後の整数列 A_1, \ldots, A_N が与えられる。これを読み込み、書き換えが発生していたかを判定し、発生していた場合にはどの整数がどの整数に書き換えられたかを報告するプログラムを作成せよ。

制約

  • 1 \leqq N \leqq 200,000
  • 1 \leqq A_i \leqq N
  • A_1, \ldots, A_N は問題文中の状況と矛盾しない。

入力

入力は以下の形式で標準入力から与えられる。

N
A_1
A_2
:
A_N

出力

書き換えが発生していなかった場合、Correct と出力せよ。

書き換えが発生していた場合、整数 x が整数 y に書き換えられたとして、y と x をこの順にスペース区切りで出力せよ。

入力例 1

6
1
5
6
3
2
6

出力例 1

6 4

元の整数列には 1 から 6 までの整数が 1 個ずつ含まれていたはずだが、入力された整数列は 6 を 2 個含み、4 を 1 個も含まない。よって、4 が 6 に書き換えられたと判定できる。

入力例 2

7
5
4
3
2
7
6
1

出力例 2

Correct

元の整数列には 1 から 7 までの整数が 1 個ずつ含まれていたはずであり、入力された整数列もこれを満たす。よって、書き換えは発生しなかったと判定できる。

Warning

Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have an integer sequence of length N stored in our server. Until just a minute ago, this sequence contained one occurrence of each integer from 1 to N.

However, trouble has occurred, which may have replaced one element in the sequence with another integer between 1 and N (inclusive). It is also possible that there was no such overwrite.

Given is the integer sequence after the trouble, A_1, \ldots, A_N. Write a program that reads it and determines whether there was an overwrite. If there was an overwrite, the program should also report which integer was replaced with which integer.

Constraints

  • 1 \leq N \leq 200000
  • 1 \leq A_i \leq N
  • The sequence A_1, \ldots, A_N is consistent with the situation described in Problem Statement.

Input

Input is given from Standard Input in the following format:

N
A_1
A_2
:
A_N

Output

If there was no overwrite, print Correct.

If there was an overwrite, let us say the integer x was replaced with the integer y. Print y and x in this order, with space in between.

Sample Input 1

6
1
5
6
3
2
6

Sample Output 1

6 4

The original sequence should have contained one occurrence of each integer from 1 to 6. However, the given sequence contains two occurrences of 6 and no occurrence of 4. Thus, we can see that 4 was replaced with 6.

Sample Input 2

7
5
4
3
2
7
6
1

Sample Output 2

Correct

The original sequence should have contained one occurrence of each integer from 1 to 7, and so does the given sequence. Thus, we can see that there was no overwrite.