The correct answer is ceil(n/3).

Proof-

Case 1- when n%3==0, select 2, 5, 8…i.e. elements which leave 2 as remainder when divided by 3.

Example- for n==6, initially 0 0 0 0 0 0

After 1st step, 1 1 1 0 0 0 (2 selected)

After 2nd step, 1 1 1 1 1 1 (5 selected)

Case 2- when n%3==1, select 1 and the last element, finally the elements 4, 7, 10 i.e. elements which divided by 3 leave remainder 1.

Example - for n=7, initially 0 0 0 0 0 0 0

After 1st step, 1 1 0 0 0 0 0 (1 selected, no i-1 present here)

After 2nd step, 1 1 0 0 0 1 1 (7 selected, no i+1 present here)

After 3rd step, 1 1 1 1 1 1 1 (4 selected)

So, basically after selecting the 1st and last element, we reduced the problem to smaller problem when n becomes divisible by 3.

Case 3- when n%3==2, select 1 and finally the elements 4, 7, 10 i.e. elements which divided by 3 leave remainder 1.

Example - for n=8, initially 0 0 0 0 0 0 0 0

After 1st step, 1 1 0 0 0 0 0 0 (1 selected, no i-1 present here)

After 2nd step, 1 1 1 1 1 0 0 0 (4 selected)

After 3rd step, 1 1 1 1 1 1 1 1 (7 selected)

So, basically after selecting the 1st we reduced the problem to smaller problem when n becomes divisible by 3.

Thus, final verdict- Hint for solving these type of questions, recursion/ dp, as these problems can be broken into smaller sub-problems which can be solved easily. Here the sub-problems were n=1, 2, 3, 4 and 5.

Also, if you want a bit tougher version of similar question, try https://www.codechef.com/problems/RNUM which was asked in Codechef Snackdown 2015: Round B.

Happy Coding…