Input 1

10
1
2
3
4
5
6
7
8
9
10

Output 1

1
2
3
4
5
6
7
8
9
12

Input 2

2
1000000
3000000

Output 2

1032857
3081672