The answer is $2n-3$. Replace $C_n$ with $n$ for convenience. We can get $2n-3$ flights by choosing $a_k=k$ and taking the path $2 \rightarrow 1\rightarrow 3 \rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow \cdots \rightarrow n \rightarrow n-1$. Assume for contracidtion that the traveler managed to take $2n-2$ flights. Reorder the countries such that $a_1 \leq a_2 \leq \ldots \leq a_n$. Let the traveler's path be $k_1 \rightarrow k_2 \rightarrow \cdots \rightarrow k_{2n+1}$. Notice that we have $a_{k_{2i-1}}+a_{k_{2i}} < a_{k_{2i}}+a_{k_{2i+1}}$ which means that $a_{k_{2i-1}} < a_{k_{2i+1}}$, which is the same as saying $k_{2i-1} <k_{2i+1}$. Therefore, $k_1,k_3,\ldots,k_{2n-1}$ is a strictly increasing sequnce of positive integers between $1$ and $n$, which means that $k_{2i-1}=i$ for all $1\leq i \leq n$. Similarly $k_2,k_4,\ldots,k_{2n-2}$ is strictly incresing. However, $k_2$ can't be neither $1$ nor $2$ as there is a flight from $k_2$ to both $1$ and $2$ (because $k_1=1,k_3=2$). Therefore, $k_2,k_4,\ldots,k_{2n-2}$ is a strictly increasing sequence of $n-1$ positive integers contained in $\{3,4,\ldots,n-1\}$, which is a contradiction.

The completed version of my solution during the exam. Answer: $2n-3$ Example: We will invoke the Greedy Algorithm. WLOG pick $$a_1+a_2<a_1+a_3<\dots<a_1+a_n<a_2+a_3<\dots<a_{n-1}+a_n.$$The following order of cities enables the traveler to attain the maximum: $$C_2\rightarrow C_1\rightarrow C_3\rightarrow C_2\rightarrow C_4\rightarrow C_3\rightarrow \dots \rightarrow C_{i+1}\rightarrow C_i\rightarrow C_{i+2}\rightarrow C_{i+1}\rightarrow\dots \rightarrow C_n\rightarrow C_{n-1}$$When counted it is apparent that $2n-3$ flights were made. Proof: Let the flight $C_i\rightarrow C_j$ be represented by the cell $(i,j)$ in a $n\times n$ square. For all $i$ paint the cells of type $(i,i)$ black. When the traveler makes the flight $C_i\rightarrow C_j$, put on the cell $(i,j)$ a $(\cdot)$ sign. Express the route the traveler took by connecting these dots on the dotted cells. According to this system, the traveler may only move to the right or move down. They may not move to the cells which are painted black. In order to make the given condition hold, for all dotted cells $(i,j)$ we paint all cells $(x,y)$ which provides $i\geq x$ and/or $j\geq y$ black. Moreover, the black cells will cut the square into two halves. It is enough to work with only one of these halves. For the sake of contradiction, assume that $Dotted Cells\geq 2n-2$ holds. We'll consider only the left half. There are $n-1$ rows in this half. There is only one available cell in the first row and it is mandatory to put a dot on it. Then for the remaining $n-2$ rows, $$\frac{DottedCells}{RowNumber}\geq\frac{2n-3}{n-2}>2$$holds. This implies from the Pigeonhole Principle that there is at least one row with $3$ dotted cells. Considering the movement abilities of the traveler we obtain that $$HorizontalMovement\geq 2(n-2)-(n-1)+3=n$$where $HorizontalMovement$ is how many cells the traveler goes through horizontally throughout their journey. However the traveler can at maximum go through $n-1$ cells horizontally in the left half of the square. This implies that our beginning assumption was false, finishing the proof. $\blacksquare$