URI Online Judge | 1645

El Dorado

Contest Local, Universidade de Ulm DE Alemanha

Timelimit: 1

Bruce Force foi a Las Vegas, o El Dorado dos apostadores. Ele está especialmente interessado em um jogo de apostas no qual uma máquina escolhe números aleatórios, formando uma sequência de n números. Cada jogador deve estimar previamente quantas subsequências crescentes de tamanho k existirão na sequência de números.

Uma subsequência de uma sequência a1,...,an é definida como ai1, ..., ail sendo que 1 ≤ i1 < i2 < ... < il ≤ n. A subsequência é crescente se aij-1 < aij para todos 1 < j ≤ l.

Bruce não confia que o Cassino contará corretamente o número de subsequências crescentes de tamanho k. Ele perguntou se você consegue resolver esse problema para ele.

Entrada

A entrada contém vários casos de teste. A primeira linha de cada caso de teste contém dois números n e k (1 ≤ kn ≤ 100), sendo que n é o tamanho da sequência escolhida pela máquina e k é o tamanho desejado das sequências crescentes. A linha seguinte deve conter n inteiros distintos dois a dois ai (-10000 ≤ ai ≤ 10000), sendo ai o i-ésimo número na sequência escolhida pela máquina.

A linha seguinte ao último caso de teste deve conter dois zeros.

Saída

Para cada caso de teste, imprimir uma linha com o número de sequências crescentes de tamanho k que a sequência de entrada contém. Você pode assumir que a maneira com que as entradas são escolhidas permite que esse número caiba em um inteiro com sinal de 64 bits (em C/C++, você pode usar o tipo de dado "long long", em java, o tipo "long").

Exemplo de Entrada Exemplo de Saída

10 5
1 2 3 4 5 6 7 8 9 10
3 2
3 2 1
0 0

252

0