Under construction

Still being built. Things may change

Cocoa... That's Not It

Time limit1.5sMemory limit1024 MB

Summary
Given the order in which Cocoa places the odd-numbered books, choose each even-numbered book so it lies strictly between its two neighbors in value.
Level

Medium6 of 10

Topics
Greedy, Sorting, Array
Solved
No attempts yet

Problem

Cocoa and Chino were looking for books in the library. Then Cocoa accidentally knocked over a bookshelf that held 2N+12N+1 books.

Luckily, each book has a number from 1 to 2N+12N+1 in order, so it was not hard to figure out the original order of the books on the shelf.

Cocoa and Chino agreed to split up the search. Cocoa found the N+1N+1 books with odd numbers, that is, the books numbered 1,3,…,2N+11, 3, \ldots, 2N+1. Chino found the NN books with even numbers, that is, the books numbered 2,4,…,2N2, 4, \ldots, 2N.

From now on, starting with Cocoa, they take turns placing the books they found, from the front. Let AiA_i be the number of the book Cocoa places at the ii-th position, and BiB_i the number of the book Chino places at the ii-th position. For every integer 1≤i≤N1 \le i \le N, book AiA_i is placed in front of book BiB_i, and book BiB_i is placed in front of book Ai+1A_{i+1}.

Cocoa does not care much about placing books in order. So after placing a book, she picks any one of the remaining books as the next one to place.

Chino wants at least a minimal order to be kept. He checks the book Cocoa picked and places a book whose number lies between the numbers of the two books Cocoa places on either side of it.

That is, for every integer 1≤i≤N1 \le i \le N, either Ai<Bi<Ai+1A_i < B_i < A_{i+1} or Ai>Bi>Ai+1A_i > B_i > A_{i+1} must hold.

Write a program that tells Chino how to place the books in this way.

Examples1

  1. Example 1

    Input
    1
    1 3
    
    Expected output
    2