Programming contests

ECN programozó csapatverseny, 2017. május 13.

May 13, 2017 10:10 AM – May 13, 2017 3:10 PM

Soaked Notes

Nerdy Bernie takes notes diligently at the university lectures and adds page numbers to his pages, starting at 1, incrementing by 1. However, on his way home, stormy winds tear his notes out of his hands, scattering the pages around him. While he is gathering his notes, the rain begins to fall, soaking some of the pages. Of course, when Bernie arrives home, he immediately starts to lay them out to dry, but the pages with page numbers blurred by the rain are no longer usable or recoverable.

Your job is to help Bernie determine those continuously numbered ranges of pages that were soaked wet in the rainstorm.

Input Specification

The first line of the input contains two integers N and M, separated by exactly one space. N represents the number of numbered pages Bernie had before leaving the university for home (0 < N < 231), and M represents the number of pages with page numbers still readable (0 ≤ M ≤ 1000 and M ≤ N).

The next line consists of exactly M different integers ai (0 < ai ≤ N, where 1 ≤ i ≤ M), representing the page numbers of the pages with page numbers still readable. Consecutive numbers are separated by a space.

Output Specification

The program should output the continuously numbered ranges of pages that were soaked wet, by printing the first and the last page number of each range, with a hyphen ('-' character) between them. Print the ranges in ascending order, one range per line. If a range contains only one page, the first and last page number should be the same.

Sample Input

  1. 10 3
  2. 1 4 9
download as text file

Output for Sample Input

  1. 2-3
  2. 5-8
  3. 10-10
download as text file
University of Debrecen; Faculty of Informatics; v. 03/01/2019