O Francisco organizou a sua coleção de canecas pela sua estante. Ele tem exatamente N canecas e a sua estante tem N prateleiras, numeradas de 1 a N de baixo para cima. Para organizar tudo, o Francisco colocou exatamente uma caneca por prateleira.
No próximo Domingo vai haver uma grande festa e todos os seus M amigos vão comparecer. O Francisco quer que cada um dos seus amigos tenha direito a uma caneca, mas nem todos conseguem chegar a todas as prateleiras. O i-ésimo amigo tem uma altura Ai, ou seja, consegue chegar a todas as prateleiras desde a primeira até à Ai. Cada amigo vai à estante buscar exatamente uma caneca, das canecas a que consegue chegar (se alguém não conseguir chegar a uma determinada prateleira, não pode pedir ajuda a um colega mais alto). Consegues determinar se existe uma forma de atribuir canecas a cada um de forma a que cada um consiga chegar à sua caneca?
Dado o número de amigos M e canecas N do Francisco e as respetivas alturas dos amigos do Francisco determinar se é possível que cada amigo fique com uma caneca a que consiga chegar.
Dois inteiros M e N numa linha, o número de amigos e canecas. De seguida vem uma linha com M inteiros com as alturas dos amigos.
Um inteiro 0 ou 1, 0 quando não há maneira de atribuir os amigos e 1 quando há.
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
| 1 ≤ M ≤ N ≤ 100 000 | Números de canecas e amigos | |
| 1 ≤ Ai ≤ 100 000 | Altura de cada amigo |
Os casos de teste deste problema estão organizados em 2 grupos com restrições adicionais diferentes:
| Grupo | Número de Pontos | Restrições adicionais |
|---|---|---|
| 1 | 40 | N, M ≤ 1000 |
| 2 | 60 | - |
4 5 5 1 3 3
1
4 5 3 1 3 3
0
6 10 2 1 3 7 4 6
1