This problem is so cute, that many algorithms may apply to it.

First let change z[1]<z[2]<...<z[n] into z[1]<=z[2]<=...<=z[n].
You can achieve it simply by replacing z[i] by z[i]-i and then 
also replacing t[i] by t[i]-i. Then what you need to do is the 
same form of the original problem except that z is non-rigorous
increasing.

Now, let us see two special case of this problem. One is t is 
rigorous decreasing, and the other is rigorous increasing. For 
the first case, obviously the answer is the median of t (For 
convenience we assume the median of t is the n/2-th biggest
number if n is even). And for the second, the answer is z[i]=t[i].
hat implication can you receive from above two facts? The algorithm 
of this problem may base on dividing t into several parts and for 
each part let z[i] be the median of this part, which makes z[i] 
increasing, of course.

Before design the algorithm let us see some facts:

Theorem 1:
For any t[1], t[2], ...,t[n], if the optimal solution is (u,u,...,
u). A solution (v,v,...,v) (v>u) is not worse than (z'[1],z'[2],
...,z'[n]) if z'[1]>v. Similarly, A solution (v,v,...,v) (v<u) is 
not worse than (z'[1],z'[2],...,z'[n]) if z'[n]<v.

Proof:
The proof can be got by taking the induction of n. Suppose it holds
for all k<n. Now we try to prove it holds for n. First change the 
solution (z'[1],z'[2],...,z'[n]) to (z'[1],z'[1],...,z'[1]) it will
be not worse because we let i be the smallest number which z'[i]>z'[1]
since changing (z'[i],z'[i+1],...,z'[n]) into (z'[1],z'[1],...,z'[1])
will make it better because of the induction hypothesis (Here, the 
median of t[i],t[i+1],...,t[n] is not greater than u, otherwise we
make the optimal solution (u,u,...,u,w,...,w), where w is the median
of t[i],t[i+1],...,t[n], which will make the optimal solution we assumed 
better) the new one is better than the former one. And if such kind 
of i does not exist, the new one is just the former one, leaving the 
solution not worse. Then we change (z'[1],z'[1],...,z'[1]) into 
(v,v,...,v). It is obvious not worse if you regard the |t[1]-x|+
|t[2]-x|+...+|z[n]-x| as the total distance of one point to n different 
points of one axis. The second half of the theorem can be proven 
similarly.

Theorem 2:
If the solution of t[1],t[2],...,t[n] is (u,u,...,u) and the solution
of t[n+1],t[n+2],...,t[n+m] is (v,v,...,v), which satisfies u>v. Then
the solution of t[1],t[2],...,t[n+m] is (w,w,...,w), where w is the 
median of t[1],t[2],...,t[n].

Proof:
First, let us find that z[n]<=u, if z[n]>u we change (z[1],z[2],...,
z[n]) to (u,u,...,u) and change (z[n+1],z[n+2],...,z[n+m]) also to
(u,u,...,u). Since (u,u,...,u) is optimal solution of the left and 
because of Theorem 1 (u,u,...,u) is not worse than (z[n+1],z[n+2],...
,z[n+m]), the new solution (u,u,...,u) is not worse than former one.
Similarly we can get z[n+1]>=v.
Then it is easy to see that the left is (z[n],z[n],...,z[n]) and 
the right is (z[n+1],z[n+1],...,z[n+1]) by Theorem 1. It is obvious 
that we make z[n] and z[n+1] both be w can lead to an optimal 
solution.

Now let us design an algorithm:

Suppose we have processed first k numbers and want to process the
(k+1)-th number. We have already known that the optimal solution of 
first k number can be represented as q[1],q[2],...,q[m] and ans[1],
ans[2],...,ans[m], which means z[q[i]]=z[q[i]+1]=...=z[q[i+1]-1]=ans[i]
(here we can consider potentially q[m+1]=k+1). We also know that for each 
interval q[i]..q[i+1]-1 the solution of this is optimal, which is always 
supposed to be true during the process of the algorithm.
When read the new number, first we regard it as in the new interval
(q[m+1]=k+1)). Obviously ans[m+1]=t[k+1]. Then if ans[m+1]>ans[m], we
can just stop because both left side and right side are optimal. What
if ans[m+1]<=ans[m]? We can combine the last two segments by Theorem 2,
set new ans[m] to the median of those t in the last two segments. 
Then we see whether ans[m]<=ans[m-1], combine it until the solution
fits the property of increasing. It is obvious that the combination takes
place at most n-1 times.

Now we need some powerful data structure to reduce the time complexity
of this algorithm. First think over which operation do you want. A 
union operation of two disjoint set and a query of the median of the
current set. First let us consider a classic data structure binary
search tree. It can be queried in O(logn) time. But what about the
union? Here let us use a trick that is to make the smaller set attach
to the bigger one. Then for each number it can be attached at most 
O(logn) times. So we have to make at most O(nlogn) insertion.
Since each insertion cost O(logn) time. The total complexity is 
O(nlogn+n(logn)^2)=O(n(logn)^2).

Here program seq_treap.pas is based on this algorithm and use a treap 
to maintain the binary search tree. However, the large coefficent of
binary search tree makes this program run slowly.

Let us get some special properties. Note that the median of each set 
can never go greater, for we always combine it with the set that has 
smaller median. Then we can just use a maximal heap to maintain the
median. That is, if the current heap contains more than half of the
total element of the set. We just simply kick the maximal number off.
Then the top of the heap is the median that we want to get. 
However, you cannot build the heap by using the linear table, for the 
physical address cannot be organised consecutively because of the 
union operation. You need a chain list to restore the structure. For 
each node, you need not only the predecessor and the successor 
pointer, but also the parent, the left child and the right child
pointer. Since n is large, you need spend a lot of memories to 
store them, and it is not easy to implement, either.

The program seq_heap.pas is based on this. Anyhow, it is quite faster
than seq_treap.pas.

Now let us have a look at an interesting improvement of this algorithm 
which leads to an O(nlogn) time complexity. Think over one fact: if we 
want to insert one number to the last interval, and the number is not 
greater than ans[p], note that whenever it is the median of its 
interval, the p-th interval must have been combined as the last interval. 
Otherwise it is smaller than ans[p], which leads to a union operation. 
Now the algorithm is based on that when we want to insert a number,
for example a[i], we do not simply insert it to the last interval, 
but to the proper interval (i.e. interval t, which satisfies 
t[i]<=ans[p], t[i]>ans[p-1]). This trick leave the union operation
out because once an element was inserted to a heap, it is always
in that heap. Once we insert, we want to process a binary search 
which takes O(logn) time. So the total time complexity is O(nlogn).

The program seq_heap2.pas is based on this. Obviously, it is faster
than seq_heap.pas.

There is another O(nlogn) algorithm which uses a kind of combinable
heap, which takes O(logn) time to combine two heaps. There is one 
kind of tree which satisfies for each node, its left subtree is not 
shallower than the right. And the key of the node is no smaller than
its children's nodes. For the union of two heaps that are rooted at
r1 and r2, if key[r1]>key[r2] you combine r2 and right[r1], as the 
new right child of r1, otherwise you combine r1 and right[r2], as
the new right child of r2. It is obvious that the total union 
operation we called is no more than the total length of the right
spine of the two heaps, which is obviously O(logn).

The program seq_union.pas describes this kind of algorithm. 
Interestingly, it is easy to implement than normal heaps. And
faster than using normal heaps.

Besides union algorithm, there is another type of algorithm which
is based on divide and conquer. The general idea of this algorithm
is to divide the whole sequence into two parts which made the first
part z[i] is not greater than x while the right part z[i] is all 
greater than x for some fixed number x. Then how to divide? Let us see a statement:

Theorem 3:
For a sequence number t[1],t[2],...,t[n] with the optimal solution 
z[1],z[2],...,z[n], the smallest i which satisfies z[i]>x is the 
smallest i which for each i<=j<=n, the median of t[i],t[i+1],...,t[j]
is greater than x.

Proof:
First, let we show that if i satisfies for any j, the median of t[i],
t[i+1],...,t[j] is greater than x, then z[i]>x. If z[i]<=x, then we
find largest number t which satisfies z[t]=x. Now we consider this 
problem in two cases: 1, if z[t+1]<=x, we set all z[i]...,z[t] to z[t+1]
with the solution not worse for we can consider it as the total distance 
to some different points to a fixed point, then we go on this process. 2, 
if z[t+1]>x, then we set z[i],z[i+1],...,z[t] a little greater than x and 
smaller than z[t+1] with the solution not worse. Hence we can get a solution
with z[i]>x. Second, we will show that if there exist an i,j satisfy the 
median of t[i], t[i+1],..., t[j] is not greater than x, then z[i]<=x. 
Otherwise let t the largest number which satisfies z[t]=z[i], we simply 
change z[i],...,z[t] to the median of t[i], t[i+1],..., t[j] to get the 
new solution that is not worse.
There is another proof which may be more simple than the above. Consider
the solution that is generated by the above algorithms. If for an i, there
is a j which satisfies the median of t[i],...,t[j] not greater than x, then
when we process the number t[j] the Positon i will be combined to the last
interval, which makes z[i]<=x. Otherwise the Positon i will never be combined
to the interval whose median is not greater than x.

Now let us design the algorithm. It is based on divide and conquer. Since
for each x, we can divides the problem into two parts with one parts the
solution not great than x and the other greater, we design the procedure 
solve(i,j,low,high:longint) that means we want to set z[i]...z[j] in the
range low..high. We can just set x to (low+high)/2. Then what is the 
efficiency of this algorithm? There is an O(n) way to find the smallest i
that is greater than x, for we can use f[i] to store the minimal value of
tot_greater(i,j)-tot_smaller(i,j) for any j>=i, here tot_greater(i,j) and 
tot_smaller(i,j) means if total number of t[i]...t[j] that is greater or 
not greater than x. Okay, let us now calculate the total time complexity
of this algorithm. We will know that for each number it will be scanned at
most logm times. So the time complexity is O(nlogm). It will be not hard 
to see that it can be simply improved to O(nlogn) by discretization since
we can simply find that the z[i] of optimal solution can be set to one of 
the value of t[1],t[2],...,t[n]. However, it is not quite significative for
in this problem logm=3/2logn, and it will cost you a lot of time to 
discretize.

Program seq_div is based on this. It is the shortest program of all.

Thanks He Lin who does a lot of work of fixing some errors of this solution.