Cookie Sigma is quite the romantic and wishes to give an amazing gift to his lover on Valentine's Day — a permutation of size $$$n$$$ $$$(2 \leq n \leq 10^5)$$$.
Let the beauty of a permutation of size $$$n$$$ be
$$$$$$ \min \limits_{1 \leq i \lt n} |a_i - a_{i+1}| $$$$$$
Cookie only wants to give a gift of the highest beauty possible to his lover. Help Cookie Sigma determine the maximum beauty of a permutation of size $$$n$$$ he could give to his lover.
$$$^\dagger$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from 1 to $$$n$$$ in any order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation (the number $$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$, but the array contains a $$$4$$$)
The first line contains one integer, $$$n$$$ $$$(2 \leq n \leq 10^5)$$$, the size of the permutation Cookie will give.
Output one number, the maximum beauty of a permutation of size $$$n$$$ Cookie Sigma can give.
2
1
4
2
In the first test case, there are only two possible permutations Cookie Sigma can make of size $$$2$$$: $$$[1,2]$$$ and $$$[2,1]$$$. In both of these, $$$|1-2| = |2-1| = 1$$$, thus $$$1$$$ is the maximum beauty of a permutation we can construct.
In the second test case, one permutation of size 4 and beauty 2 is $$$[3,1,4,2]$$$. $$$|3-1| = 2$$$, $$$|1-4| = 3$$$, $$$|4-2| = 2$$$. The minimum of these is $$$2$$$, thus this is the beauty of our permutation. It can be proven that for $$$n=4$$$ there is no permutation of beauty $$$ \gt 2$$$.
