没错，今天又下雨了，而且4眼鸟昨天比赛写的还是很差，心里还是不太高兴，于是他又用家里祖传的调理心态的办法，发呆看蚂蚁来调整心态啦！很巧，真的很巧，由于下雨的原因，路上再一次出现了很深的积水，有一根长为L的木棍刚好完全横跨积水，4眼鸟发现木棍上有N只蚂蚁在爬，每只蚂蚁都以每秒一个单位的速度往前爬，但是由于木棍太细了，蚂蚁不能够并排爬行，也不能够交错而过，当两只蚂蚁迎面遇上时，两只蚂蚁都会选择立刻掉头且速度不变继续爬行，但是，由于现在还在下雨，4眼鸟第一时间不能确定蚂蚁是向哪个方向移动的了，所以这回想知道的事情不一样了！他想知道，是否所有的蚂蚁都能成功爬离木棍呢？如果能，他想知道最少所有蚂蚁需要多少时间？最长需要多少时间呢？

Input

第一行共一个整数 L，表示木棍的长度。 第二行共一个整数 N，表示初始时在木棍上的蚂蚁个数。 第三行共有 N 个整数，分别表示每个蚂蚁的初始坐标。 所有输入均小于1e5.

Output

共一行，输出 2 个整数，分别表示蚂蚁全部离开木棍的最小时间和最大时间。2 个整数由一个空格符分开。如果有蚂蚁不能成功离开木棍，则输出两个 -1

Samples

4
2
1 3

2 4

提示

当蚂蚁位于坐标0或者L+1时视为离开木棍