RO-TST 2003 Problem 17

A permutation $\sigma: \{1,2,\ldots,n\}\to\{1,2,\ldots,n\}$ is called straight if and only if for each integer $k$ , $1\leq k\leq n-1$ the following inequality is fulfilled $$|\sigma(k)-\sigma(k+1)|\leq 2.$$ Find the smallest positive integer $n$ for which there exist at least 2003 straight permutations.

Valentin Vornicu