Điền mảng theo đoạn ưu tiên

Bối cảnh và bài toán

Ban đầu mảng a[1..n] toàn 0. Ở bước v=1..n, chọn đoạn 0 liên tiếp dài nhất; nếu có nhiều đoạn cùng độ dài, chọn đoạn có l nhỏ nhất. Với đoạn [l,r], đặt a[(l+r)/2]=v (chia nguyên xuống), khiến đoạn tách thành tối đa hai đoạn con chưa điền.

Yêu cầu

In mảng sau n bước.

Input

• Một dòng chứa n.

Output

In n giá trị của mảng cuối.

Ràng buộc

• 1 <= n <= 2 * 10^5

Chấm điểm

Ví dụ 1

Input

5

Output

2 4 1 3 5

Giải thích. Đầu tiên chọn [1,5] đặt 1 ở 3; sau đó [1,2] đặt2 ở1; [4,5] đặt3 ở4; ...

Ví dụ 2

Input

3

Output

2 1 3

Giải thích. Chọn [1,3] trước, rồi hai đoạn đơn [1,1] và [3,3] theo l nhỏ hơn.

Thông tin bài tập

Nguồn: Phỏng theo Codeforces 1353D – Constructing the Array.

Tham khảo: https://codeforces.com/problemset/problem/1353/D