Minimum number of times monkey must travel While working on an unrelated subject, I found a problem which could be alternatively be stated as the following:

A monkey must travel a path of length $n-1$, from $a_1$ to $a_n$. On every turn, he may jump any distance forward, but cannot go backwards. He may jump any number of times. How many times must he travel the path so that he has jumped at least once from $a_i$ to $a_j$ for all $1\leq i\lt j\leq n$? (After reaching $a_n$, one travel is completed and he starts again from $a_1$.)

The solution to the original problem (in chemistry) was done by brute force, but I am hoping to discover an expression in $n$.

My attempts
Suppose the number of such paths is $f(n)$. Then for a path to $a_{n+1}$, it must be $f(n+1)$. This can be achieved in the following method:
Jump $1$ unit, then jump in the $f(n)$ ways. Then jump $2$, then in $f(n-1)$ ways. And so on, thus getting $f(n+1)=\sum_1^nf(k)$. But this is wrong, as a lot of these paths overlap, and I can find no way of figuring out how many.
So I tried reformulation, again.

Take series $\langle a_n\rangle_1^n$ of whole numbers such that $\sum a_k=n$. Every nonzero element appears before every zero element. What is the minimum number of such series which must be taken, such that for every $i\geq1$, $a_{n-i}$ is equal to every number from $1$ to $i$ in at least one of them? 

There are, I believe, formulas for the breaking of natural numbers into a sum of whole numbers, but here the conditions are different, and the order too matters. I am unsure of where to go from here.
Please help.
 A: There was an answer here a few hours ago claiming $n^2/4.$  I did not read it in full, and I do not know why it's been deleted.  But I think the claim is correct.  The minimum number of travels is ${n^2\over 4}$ for even $n$, and ${n^2-1 \over 4}$ for odd $n$.
(Credits: the necessity argument I stole from the now-deleted post.  The sufficieny part is my own - I didn't get a chance to read that part of the deleted post and have no idea if its argument is same as mine.)
Necessity: For each $a_i$ among the $\lfloor n/2 \rfloor$ nodes in the first half, and each $a_j$ among the $\lceil n/2 \rceil$ nodes in the second half, there is one jump $(a_i, a_j)$.  None of these jumps can share the same travel.  So the number of travels $\ge \lfloor n/2 \rfloor \lceil n/2 \rceil = {n^2 \over 4}$ (if $n$ is even) or ${n^2 - 1 \over 4}$ (if $n$ is odd).
Sufficiency, via explicit construction: 
In round $1$, we do all jumps of the form $(a_1, a_i)$ and $(a_i, a_n)$.  These can be assembled into $n-1$ travels as follows: the direct jump $(a_1, a_n)$, and, the two-hop path $((a_1, a_i), (a_i, a_n))$ for all $i \in [2,n-1]$.  Since there are $n-2$ choices for $i\in [2,n-1]$, plus the direct jump, the total number of travels is $n-1$.
In round $2$, we do all jumps of the form $(a_2, a_i)$ and $(a_i, a_{n-1})$.  By the same argument as above, there are $n-4$ choices for $i \in [3, n-2]$, plus the direct jump $(a_2, a_{n-1})$, for a total of $n-3$ travels.  (Obviously, for each travel we need to attach $(a_1, a_2)$ at the front and $(a_{n-1}, a_n)$ at the back.)
In general, in round $k$, we do all jumps of the form $(a_k, a_i)$ and $(a_i, a_{n-k+1})$, for a total of $n-2k+1$ travels.  (Obviously, for each travel we need to attach $(a_1, a_k)$ at the front and $(a_{n-k+1}, a_n)$ at the back.)
We keep doing this as long as $k < n-k+1$.  


*

*For even $n$, this means $k \le {n \over 2}$ (entire first half), and $n-k+1 \ge {n \over 2} + 1$ (entire second half).

*For odd $n$, this means the midpoint ${n+1\over 2}$ is never either $k$ or $n-k+1$.  We have: $k \le {n+1 \over 2} - 1$ (entire first half, exclude midpoint), and $n-k+1 \ge {n+1 \over 2} +1$ (entire second half, exclude midpoint).
Claim: After we do this for all rounds, all jumps have now been used.  
Proof: consider any jump $(a_p, a_q)$.  Either $p$ is in the first half (exclude midpoint if $n$ odd), or $q$ is in the second half (exclude midpoint if $n$ odd).  Thus, this jump has been used in some round.  Note that if $n$ is odd and $p$ or $q$ is the midpoint, the argument still applies to the other point.
Summing up all rounds, the total number of travels $=f(n) = (n-1) + (n-3) + (n-5) + \dots$


*

*Even $n=2m: f(n) = (2m-1) + (2(m-1)-1) + \dots + 5 + 3 + 1 = m^2 = {n^2 \over 4}$.

*Odd $n=2m+1: f(n) = 2m + \dots + 4 + 2 = 2(m + \dots + 2 + 1) = m(m+1) = {n^2 -1 \over 4}$.
A: There is a relatively straightforward lower bound.
Look at the total length of all the jumps that the monkey needs to do. There is just $1$ jump of length $n-1$ (going from $a_1$ to $a_n$), there are $2$ of length $n-2$, $3$ of length $n-3$, etc. The total length $L$ of all the jumps is therefore:
$$L = \sum_{i=1}^{n-1} {i(n-i)} = \frac{(n-1)n(n+1)}{6}$$
Each traversal of the path is of length $n-1$, so the number of traversals T is at least $L/(n-1)$:
$$T = \frac{L}{n-1} = \frac{n(n+1)}{6}$$
This is only a simple lower bound, and can only be reached for very small values of $n$.
The problem is that there are only $n-1$ possible jumps that start from $a_1$, and every traversal must include one. For larger $n$ you obviously have $T>n-1$, so the monkey will have to repeat jumps. Also, there is only one jump landing on $a_2$, but there are $n-2$ leaving it, so  for $n>3$ there must again be repeat jumps.
This means that the lower bound gets more inaccurate for larger $n$, but I have not tried to quantify by how much.
