We claim that the answer is $\lceil \dfrac{3n}{2} \rceil -1$. We depict the set $M$ as the set of all points $(i,j)$, with $0 \leq i <j \leq n-1$, thus forming a "staircase" in which we must find the maximum number of points one can select such that for each point, if we form the staircase obtained by looking at all points which have a greater (or equal) $x-$ coordinate and a smaller (or equal) $y-$ coordinate, then this staircase contains at most one extra point. Bound: Note that each line of the staircase can contain at most $2$ marked points. Assume that $t$ of the lines contain exactly $2$ points. We claim that $t \leq \lfloor \dfrac{n-1}{2} \rfloor$. Indeed, consider all lines $\ell_1, \ell_2, \ldots, \ell_t$ which have exactly two marked points. Consider the position of the two marked points on line $\ell_1$. From the given condition, it is easy to observe that the two marked points of line $\ell_2$ must both have a (strictly) greater $x-$ coordinate than the points on line $\ell_1$ (some figures would help here). Continuing this argument, and taking into account that the first line cannot contain two marked points (as it only has $1$ in total), we obtain that $2t \leq n-1$, as desired. Hence, for the total number of points we obtain that $s \leq 2t+(n-t)=n+t \leq n+\lfloor \dfrac{n-1}{2} \rfloor=\lceil \dfrac{3n}{2} \rceil -1,$ as desired. Construction: For the construction, we may just select points $(0,n-1), (0,n-2), (1,n-3), (2,n-3), (2,n-4), (3,n-5), (4,n-5), (4,n-6), \ldots,$ and so on (that is, the even $x-$ coordinates appear two times, while the odd $x-$ coordinates appear once, while $y-$ coordinates appear twice every three points). It is easy to see that this construction works, and produces exactly that many points (again, a figure would greatly help).