Instead of being a skillful warrior capable of slaying Hydras (see here and here), this time you are a warrior that has no prior knowledge on how to kill one or which weapons to use against the creature.

In this problem, whenever you cut a single head off, two will grow in the same place. Since you don't have the mechanism to cut many heads off simultaneously, the number of heads will only grow. In this case, our Hydra can start with N (N ⩾ 1) heads. Let's call the first encounter a generation and we will represent the heads from the first generation as 0, the heads created after the first blow as 1, and so on.

Input

You will be given an integer N representing how many heads the Hydra initially have and a list of size N containing in which index (in the examples I will use 0-indexed format) you will cut a head off. You can always assume the indexes given are valid - remember that the list (i.e.: the heads) will grow as you cut heads off.

Example

Input: N = 4 and [0,4,2,5]

Generation 0 - Attack index 0

0 0 0 0 => 1 1 0 0 0
^ ^ ^

Generation 1 - Attack index 4

1 1 0 0 0 => 1 1 0 0 2 2
 ^ ^ ^

Generation 2 - Attack index 2

1 1 0 0 2 2 => 1 1 3 3 0 2 2
 ^ ^ ^

Generation 3 - Attack index 5

1 1 3 3 0 2 2 => 1 1 3 3 0 4 4 2
 ^ ^ ^

Last generation

1 1 3 3 0 4 4 2

As you can see, the indexes given are related to the list of the previous generation.

Output

You are required to output the last generation.

Test cases

N = 1 and [0] => [1,1]
N = 2 and [0,0] => [2,2,1,0]
N = 2 and [0,1] => [1,2,2,0]
N = 2 and [1,0] => [2,2,1,1]
N = 2 and [1,1] => [0,2,2,1]
N = 4 and [0,4,2,5] => [1,1,3,3,0,4,4,2]
N = 6 and [0,0,0,0,0,0] => [6, 6, 5, 4, 3, 2, 1, 0, 0, 0, 0, 0]
N = 6 and [5,6,7,8,9,10] => [0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 6]
N = 10 and [1,7,3,12,9,0,15,2,2,10] => [6, 6, 9, 9, 8, 1, 3, 3, 0, 0, 10, 10, 2, 5, 5, 0, 0, 4, 7, 7]

This is code-golf so shortest answer in bytes wins!

Japt, 14 bytes

rÈhY[°TT] cUî

Try it

JavaScript (ES6),  61 59  51 bytes

Thanks to @Shaggy for point out that n is useless, saving 8 bytes in both versions

Expects the array in 0-indexed format. Ignores n.

a=>a.map(i=>b.splice(i,1,++g,g),b=a.map(_=>g=0))&&b

Try it online!

JavaScript (Node.js),  64  56 bytes

Using reduce() and flat():

a=>a.reduce((b,i,g)=>b.flat(1,b[i]=[++g,g]),a.map(_=>0))

Try it online!

Python 2, 60 bytes

H,a=input()
H=[0]*H
for i in a:H[i:i+1]=[max(H)+1]*2
print H

Try it online!

Python 2, 60 bytes

n,a=input()
h=[0]*n
for c in a:h[c:c+1]=[max(h)+1]*2
print h

Try it online!

Retina 0.8.2, 69 bytes

d+
$*_
r`_G
,0
+`^((,*)_)(_)*(.*,,(?<-3>d+,)*)d+
$2$4$.1,$.1
^,+

Try it online! Link includes test cases. 1-indexed. Takes input as ...list,N. Does not require the list to be of length N. Explanation:

d+
$*_

Convert all of the inputs to unary, but using _, so that it doesn't get confused with later uses of the digit 1. (Retina 1 would do this automatically for a 2-byte saving.)

r`_G
,0

Replace N with an array of N zeros, but don't alter the list.

+`

Process all elements of the list.

^((,*)_)(_)*(.*,,(?<-3>d+,)*)d+

Find the next element of the list and the equivalent position in the array. $1 = current generation (as a length), $2 = commas from previous generations, $3 = current index - 1, $4 = first $3 heads.

$2$4$.1,$.1

Replace the head at the current index with two copies of the current generation in decimal.