VMO 1996 Problem 3

Let be given integers k and n such that 1<=k<=n. Find the number of ordered k-tuples (a_1,a_2,...,a_n), where a_1, a_2, ..., a_k are different and in the set {1,2,...,n}, satisfying

1. There exist s, t such that 1<=s<t<=k and a_s>a_t.
2. There exists s such that 1<=s<=k and a_s is not congruent to s mod 2.

P.S. This is the only problem from VMO 1996 I cannot find a solution or I cannot solve. But I'm not good at all in combinatoric...