Different Adjacent
Обмеження: 2 сек., 512 МіБ
You are given a sequence a of n integers.
Construct a sequence b of n integers satisfying the following conditions.
bi≥ai for all 1≤i≤n.
Adjacent elements of b are distinct.
max1≤i≤n(bi−ai) is minimum possible.
Вхідні дані
The first line contains an integer n – the number of elements in sequence a.
The second line contains n integers ai – the elements of sequence a.
Вихідні дані
Print n integers bi – elements of sequence b.
Обмеження
1≤n≤2⋅105,
1≤ai≤109.
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
4 4 7 4 7 | 4 7 4 7 |
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
7 4 4 4 4 4 4 4 | 5 4 5 4 5 4 5 |
Примітки
In the first example, it is possible to make b=a. In this case, max1≤i≤n(bi−ai)=0.
In the second example, max1≤i≤n(bi−ai)=1.
Джерело: Ukrainian National Programming Contest 2024 - Stage 2