3. Let integer $n(n \geqslant 5)$. Find the maximum integer $k$, such that there exists an $n$-sided polygon (convex or concave, as long as the boundary does not intersect itself) with $k$ right angles.
(Lithuania provided)
Solution: We prove that when $n=5$, the satisfying $k$ equals 3; when $n \geqslant 6$, $k$ equals $\left[\frac{2 n}{3}\right]+1$ (where $[x]$ represents the greatest integer not exceeding $x$).

Assume there exists an $n$-sided polygon with $k$ right angles, since all other angles are less than $360^{\circ}$, we have
$$
(n-k) \times 360^{\circ}+k \times 90^{\circ}>(n-2) \times 180^{\circ},
$$

which means $k<\frac{2 n+4}{3}$.
Since $k$ and $n$ are integers, therefore,
$$
k \leqslant\left[\frac{2 n}{3}\right]+1 \text {. }
$$

If $n=5$, then $\left[\frac{2 n}{3}\right]+1=4$. However, if a pentagon has 4 right angles, then the other angle would be $180^{\circ}$, which is a contradiction.

Figure 12 shows a pentagon with 3 right angles, so the maximum integer $k=3$.

For $n \geqslant 6$, we construct an $n$-sided polygon with $\left[\frac{2 n}{3}\right]+1$ right angles.
Figure 13 provides examples for $n=6,7,8$.
For $n \geqslant 9$, we will construct examples inductively.
For all interior angles greater than $180^{\circ}$, we can cut out a "triangle with one less vertex" to add three vertices and two right angles, as shown in Figure 14. Figure 15 shows another construction method.