Escrito por Enzo Dantas
Conhecimento prévio necessário:
De acordo com a definição do problema, a diferença entre dois termos consecutivos deve ser maior que 1. Sendo assim, uma ideia simples que pode ser testada é fazer essa diferença ser igual a 2. Ou seja, vamos explorar a ideia de criar uma permutação tal que a diferença entre elementos consecutivos é igual a 2. Começando a sequência com o número 1, os próximos elementos serão 3, 5, 7, 9, etc. Ou seja, os números ímpares menores ou iguais a 
. E quando acabarem os números ímpares? Vamos fazer a mesma coisa com os números pares, ou seja, vamos começar com 2 e ir subindo para 4, 6, 8, 10, etc. Tendo essas duas sequências, como juntar elas em uma só tal que a condição ainda é válida? Vamos tentar colocar o maior par ao lado do menor ímpar, assim a diferença será a maior possível na junção das duas sequências. Logo, vamos colocar todos os pares primeiro e todos os ímpares depois.
Exemplo para 
Fica como exercício para o leitor descobrir o motivo de ser ligeiramente melhor colocar os pares primeiro em vez de os ímpares primeiro.
Por fim, é necessário lidar com os casos que não possuem solução. Para qualquer caso tal que a diferença entre o maior par e o menor ímpar é maior que 1, existe solução. Ou seja, para qualquer N>=4 existe solução. Restam apenas três casos, e é fácil de conferir manualmente que para 
e 
não existe solução, enquanto que para 
a solução é apenas o número 1.
Recomendamos que você tente implementar o problema antes de ver o código.Veja a implementação nesse link.