Construct the Lexicographically Largest Valid Sequence

Difficulty: Medium

Problem Statement

Given an integer n, find a sequence that satisfies all of the following:

• The integer 1 occurs once in the sequence.
• Each integer between 2 and n occurs twice in the sequence.
• For every integer i between 2 and n, the distance between the two occurrences of i is exactly i.
• The distance between two numbers in the sequence, a[i] and a[j], is defined as |j - i|.

Return the lexicographically largest sequence. It is guaranteed that a solution always exists.

A sequence a is lexicographically larger than a sequence b (of the same length) if in the first position where a and b differ, a has a number greater than the corresponding number in b.

For example, [0,1,9,0] is lexicographically larger than [0,1,5,6] because the first position they differ is at the third number, and 9 is greater than 5.

---

Example 1

Input:

n = 3

Output:

[3,1,2,3,2]

Explanation:

• [2,3,2,1,3] is also a valid sequence, but [3,1,2,3,2] is lexicographically larger.

---

Example 2

Input:

n = 5

Output:

[5,3,1,4,3,5,2,4,2]

---

Example 3

Input:

n = 4

Output:

[4,2,3,2,1,3,4]

---

Constraints

• 1 <= n <= 20