This question is of course inspired by the question How to solve f(f(x))=cosx
and Joel David Hamkins' answer, which somehow gives a formal trick for solving equations of the form $f(f(x))=g(x)$ on a bounded interval. [EDIT: actually he can do rather better than this, solving the equation away from a bounded interval (with positive measure)].

I've always found such questions ("solve $f(f(x))=g(x)$") rather vague because I always suspect that solutions are highly non-unique, but here are two precise questions which presumably are both very well-known:

Q1) Say $g:\mathbf{R}\to\mathbf{R}$ is an arbitrary function. Is there always a function $f:\mathbf{R}\to\mathbf{R}$ such that $f(f(x))=g(x)$ for all $x\in\mathbf{R}$?

Q2) If $g$ is as above but also assumed continuous, is there always a continuous $f$ as above?

The reason I'm asking is that these questions are surely standard, and perhaps even easy, but I feel like I know essentially nothing about them. Apologies in advance if there is a well-known counterexample to everything. Of course Q1 has nothing to do with the real numbers; there is a version of Q1 for every cardinal and it's really a question in combinatorics.

EDIT: Sergei Ivanov has answered both of these questions, and Gabriel Benamy has raised another, which I shall append to this one because I only asked it under an hour ago:

Q3) if $g$ is now a continuous function $\mathbf{C}\to\mathbf{C}$, is there always continuous $f$ with $f(f(x))=g(x)$ for all $x\in\mathbf{C}$?

EDIT: in the comments under his answer Sergei does this one too, and even gives an example of a continuous $g$ for which no $f$, continuous or not, can exist.

Related MO questions: f(f(x))=exp(x) and other functions just in the middle between linear and exponential, and Does the exponential function has a square root.

Q1: No. Let $g(0)=1, g(1)=0$ and $g(x)=x$ for all $x\in\mathbb R\setminus\{0,1\}$.
Assuming $f\circ f=g$, let $a=f(0)$, then $f(a)=1$ and $f(1)=g(a)=a$ since $a\notin\{0,1\}$.
Then $g(1)=f(f(1))=f(a)=1$, a contradiction.

Q2: No. Let $g(x)=-x$ or, in fact, any decreasing function $\mathbb R\to\mathbb R$. Then $f$ must be injective and hence monotone. Whether $f$ is increasing or decreasing, $f\circ f$ is increasing.
