Bump....

I think the answer is $250998$ by lining them up $500,499,\dots,2,1,1000,999,\dots,502,501$, but can not seem to prove it.

Bump... Does anyone have a solution?

Beautiful Problem! We claim that the answer for $2n$ is $(n+1)^2-3$. Construction: Let the children be $1,2 \cdots 2n$ in descending order of height. Arrange like $$n+1,n+2,\cdots,2n,1,2,\cdots,n$$. Any pair $(i,j)$ so that $i<j$ or $j=i+1$ will be good, so it works. Bound: We induct on $n$ with base case trivial by brute force. Claim: Let $(Y,Z)$ be the smallest good pair where $Y < Z$ (the smallest means that for all other good pairs $A < B$, the child $Y$ is less than $A$). The number of children $X$ so that $(X,Y)$ and $(X,Z)$ both are good is atmost $2$. Proof: If $X$ lies between $Y,Z$ then this contradicts minimality of the good pair, therefore $X$ lies on the left of $Y$ or right of $Z$. Assume there are two children so that they both form pairs with $Y,Z$ and lie to the left of $Y$ (similarly follows for right of $Z$), call them $C_1,C_2$, then $Y<C_1<C_2<Z$, however this means that $C_2$ lies between $C_1$ and $Z$ which implies that $(C_1,Z)$ is not a good pair, contradiction! and therefore there can lie atmost one such $X$ on either side, which yields us our claim. Now, remove $(Y,Z)$ from the group of children and by Induction Hypothesis we have atmost $n^2+3$ good pairs. Now as there are $2n-2$ people apart from $Y,Z$ and $Y,Z$ can share atmost two people, so we have at most $$n^2-3+2n+1 = (n+1)^2-3$$