Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
長さ N の整数列 A=(A_1,A_2,\cdots,A_N) が与えられます.
すぬけくんは今から, A の中から一つ値を選びます. ここで選んだ値を x とします. そして,A の要素のうち,x でないものを元の順番を保ったまま並べ,整数列 a を作ります.
a としてありうる数列のうち,辞書順最小のものを求めてください.
制約
- 1 \leq N \leq 200000
- 1 \leq A_i \leq N
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる.
N A_1 A_2 \cdots A_N
出力
辞書順最小の a の要素を空白区切りで出力せよ.
入力例 1
5 2 4 4 1 2
出力例 1
2 1 2
例えば,x=2 とすると,a=(4,4,1) となります. また,x=4 とすると,a=(2,1,2) となり,これは辞書順最小です.
入力例 2
3 1 1 1
出力例 2
x=1 とすると a は空になり,これは明らかに辞書順最小です. なお,出力に余計な空白や改行が含まれていても構いません.
入力例 3
5 1 1 2 3 3
出力例 3
1 1 2
Score : 300 points
Problem Statement
Given is a sequence of N integers A=(A_1,A_2,\cdots,A_N).
Snuke now chooses a value in A. Let x be the value chosen. Then, he makes an integer sequence a by lining up all elements of A that are not x without changing the order.
Find the lexicographically smallest sequence that can be obtained as a.
Constraints
- 1 \leq N \leq 200000
- 1 \leq A_i \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
Print the elements of the lexicographically smallest a, separated by spaces.
Sample Input 1
5 2 4 4 1 2
Sample Output 1
2 1 2
For example, when x=2, we will have a=(4,4,1). When x=4, we will have a=(2,1,2), which is the lexicographically smallest.
Sample Input 2
3 1 1 1
Sample Output 2
When x=1, a will be empty, which is obviously the lexicographically smallest. As a side note, the output may contain additional spaces or newlines.
Sample Input 3
5 1 1 2 3 3
Sample Output 3
1 1 2