Sequences with no wells X41088


Statement
 

pdf   zip

A sequence of numbers has a well if it contains three consecutive numbers such that that the endpoints add up more than twice the one in the middle.

Formally, (x1,x2,…,xn)(x_1, x_2 , \ldots , x_n) has a well if it exists at least an ii with 1≤i<n−11 \leq i < n - 1 such that xi+xi+2>2⋅xi+1x_i + x_{i+2} > 2\cdot x_{i+1}.

Write a program that, given an integer n≥1n \geq 1, writes all sequences with no well that can be obtained by reordering the sequence (1,2,…,n)(1, 2, \ldots , n).

Input

The input consists of an integer n≥1n \geq 1.

Output

Write all sequences with no well that can be obtained by reordering the sequence (1,2,…,n)(1, 2, \ldots, n). You can write the sequences in any order.

Public test cases

  • Input

    3

    Output

    (1,2,3)
(1,3,2)
(2,3,1)
(3,2,1)

  • Input

    2

    Output

    (1,2)
(2,1)

  • Input

    4

    Output

    (1,2,3,4)
(1,3,4,2)
(1,4,3,2)
(2,3,4,1)
(2,4,3,1)
(4,3,2,1)

  • Input

    1

    Output

    (1)
    • Information
    Author
    Language
    English
    Translator
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python