시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 347 225 209 68.301%

문제

준하는 라디오 수집광으로 신제품의 라디오가 나올때마다 흥분을 금치 못한다고 한다.

최근 준하가 구입한 라디오는 매우 하이테크 한데, 그 라디오에는 다음과 같은 버튼이 있다.

  • 첫번째 버튼은 주파수를 1MHz 증가시킨다.
  • 두번째 버튼은 주파수를 1MHz 감소시킨다.
  • 나머지 N개의 버튼은 즐겨찾기 기능으로, 미리 지정된 주파수로 이동한다.

준하는 몸이 안좋아 하루에 손가락을 몇 번 움직이지 못하기 때문에 우리의 도움이 필요하다.

현재 주파수 A와 듣고싶은 주파수 B가 주어질 때, 

주파수 A에서 B로 갈 때 눌러야 하는 가장 적은 버튼수를 구해주자.

입력

첫 줄엔 정수 A와 B가 주어진다 (1 ≤ A, B < 1000, A ≠ B).

다음 줄엔 정수 N이 주어진다 (1 ≤ N ≤ 5).

다음 N개의 줄엔 미리 지정되어 있는 주파수가 주어진다 (주파수는 1000 보다 작다).

출력

주파수 A에서 B로 갈 때 눌러야 하는 버튼수의 최솟값을 출력한다.

예제 입력 1

88 17
3
18
1
42

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjMxMzUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI3N2NcdWI1MTRcdWM2MjQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzkwMFx1ZDU1OFx1YjI5NCBcdWI3N2NcdWI1MTRcdWM2MjQgXHVjMjE4XHVjOWQxXHVhZDExXHVjNzNjXHViODVjIFx1YzJlMFx1YzgxY1x1ZDQ4OFx1Yzc1OCBcdWI3N2NcdWI1MTRcdWM2MjRcdWFjMDAgXHViMDk4XHVjNjJjXHViNTRjXHViOWM4XHViMmU0IFx1ZDc2NVx1YmQ4NFx1Yzc0NCBcdWFlMDhcdWNlNTgmbmJzcDtcdWJhYmJcdWQ1NWNcdWIyZTRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNkNWNcdWFkZmMgXHVjOTAwXHVkNTU4XHVhYzAwIFx1YWQ2Y1x1Yzc4NVx1ZDU1YyBcdWI3N2NcdWI1MTRcdWM2MjRcdWIyOTQgXHViOWU0XHVjNmIwIFx1ZDU1OFx1Yzc3NFx1ZDE0Y1x1ZDA2YyBcdWQ1NWNcdWIzNzAsIFx1YWRmOCBcdWI3N2NcdWI1MTRcdWM2MjRcdWM1ZDBcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWJjODRcdWQyYmNcdWM3NzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1Y2NhYlx1YmM4OFx1YzlmOCBcdWJjODRcdWQyYmNcdWM3NDAgXHVjOGZjXHVkMzBjXHVjMjE4XHViOTdjIDFNSHogXHVjOTlkXHVhYzAwXHVjMmRjXHVkMGE4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI0NTBcdWJjODhcdWM5ZjggXHViYzg0XHVkMmJjXHVjNzQwIFx1YzhmY1x1ZDMwY1x1YzIxOFx1Yjk3YyAxTUh6IFx1YWMxMFx1YzE4Y1x1YzJkY1x1ZDBhOFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViMDk4XHViYTM4XHVjOWMwIE5cdWFjMWNcdWM3NTggXHViYzg0XHVkMmJjXHVjNzQwIFx1Yzk5MFx1YWNhOFx1Y2MzZVx1YWUzMCBcdWFlMzBcdWIyYTVcdWM3M2NcdWI4NWMsIFx1YmJmOFx1YjlhYyBcdWM5YzBcdWM4MTVcdWI0MWMgXHVjOGZjXHVkMzBjXHVjMjE4XHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM5MDBcdWQ1NThcdWIyOTQgXHViYWI4XHVjNzc0IFx1YzU0OFx1Yzg4Ylx1YzU0NCZuYnNwO1x1ZDU1OFx1YjhlOFx1YzVkMCBcdWMxOTBcdWFjMDBcdWI3N2RcdWM3NDQgXHViYTg3Jm5ic3A7XHViYzg4IFx1YzZjMFx1YzljMVx1Yzc3NFx1YzljMCBcdWJhYmJcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzZiMFx1YjlhY1x1Yzc1OCBcdWIzYzRcdWM2YzBcdWM3NzQgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ2MDRcdWM3YWMmbmJzcDtcdWM4ZmNcdWQzMGNcdWMyMTggQVx1YzY0MCBcdWI0ZTNcdWFjZTBcdWMyZjZcdWM3NDAgXHVjOGZjXHVkMzBjXHVjMjE4IEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YywmbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjOGZjXHVkMzBjXHVjMjE4IEFcdWM1ZDBcdWMxMWMgQlx1Yjg1YyBcdWFjMDggXHViNTRjIFx1YjIwY1x1YjdlY1x1YzU3YyBcdWQ1NThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzgwMVx1Yzc0MCBcdWJjODRcdWQyYmNcdWMyMThcdWI5N2MmbmJzcDtcdWFkNmNcdWQ1NzRcdWM4ZmNcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWImbmJzcDtcdWM5MDRcdWM1ZDQgXHVjODE1XHVjMjE4Jm5ic3A7QVx1YzY0MCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCAoMSAmbGU7IEEsIEIgJmx0OyAxMDAwLCBBICZuZTsgQikuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyZuYnNwO1x1YzkwNFx1YzVkNCBcdWM4MTVcdWMyMTgmbmJzcDtOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCAoMSAmbGU7IE4gJmxlOyA1KS48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQ0IFx1YmJmOFx1YjlhYyBcdWM5YzBcdWM4MTVcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1YzhmY1x1ZDMwY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQmbmJzcDsoXHVjOGZjXHVkMzBjXHVjMjE4XHViMjk0Jm5ic3A7MTAwMCBcdWJjZjRcdWIyZTQgXHVjNzkxXHViMmU0KS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4ZmNcdWQzMGNcdWMyMTggQVx1YzVkMFx1YzExYyBCXHViODVjIFx1YWMwOCBcdWI1NGMgXHViMjBjXHViN2VjXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWJjODRcdWQyYmNcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMTM1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUkFESU8iLCJkZXNjcmlwdGlvbiI6IjxwPlNsYXZrbyBpcyBkcml2aW5nIGhpcyBuZXcgS2FyYW1ib2wgR1QyMCBjYXIgd2l0aCBhIHRvcC1vZi10aGUtbGluZSByYWRpbyAod2hpY2gsIG9mIGNvdXJzZSwgU2xhdmtvIG1hZGUgaGltc2VsZiBpbiBoaXMgYmFzZW1lbnQsIG5leHQgdG8gdGhlIGxhdW5kcnkgd2FzaGVyKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+U2xhdmtvJiMzOTtzIHJhZGlvIGlzIHZlcnkgaGktdGVjaCBhbmQgaXMgZXF1aXBwZWQgd2l0aCB0d28gYnV0dG9ucyB0aGF0IGFyZSB1c2VkIHRvIG1hbnVhbGx5IGNoYW5nZSB0aGUgZnJlcXVlbmN5LCBhbmQgc2V2ZXJhbCBidXR0b25zIHRoYXQgY2hhbmdlIHRoZSBmcmVxdWVuY3kgdG8gb25lIG9mIHRoZSBwcmVkZWZpbmVkIGZyZXF1ZW5jaWVzLiBNb3JlIHByZWNpc2VseTombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgZmlyc3QgYnV0dG9uIGluY3JlYXNlcyB0aGUgZnJlcXVlbmN5IGJ5IDEgKG9uZSkgTUh6OyZuYnNwOzxcL2xpPlxyXG5cdDxsaT5UaGUgc2Vjb25kIGJ1dHRvbiBkZWNyZWFzZXMgdGhlIGZyZXF1ZW5jeSBieSAxIChvbmUpIE1IejsmbmJzcDs8XC9saT5cclxuXHQ8bGk+RWFjaCBvZiB0aGUgcmVtYWluaW5nIE4gYnV0dG9ucyBjaGFuZ2VzIHRoZSBmcmVxdWVuY3kgdG8gb25lIG9mIHRoZSBOIHByZWRlZmluZWQgZnJlcXVlbmNpZXMuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+WW91ciBqb2IgaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQsIGdpdmVuIHR3byBmcmVxdWVuY2llcyBBIGFuZCBCLCBjb21wdXRlcyB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIGJ1dHRvbiBwcmVzc2VzIG5lZWRlZCB0byBjaGFuZ2UgdGhlIGZyZXF1ZW5jeSBmcm9tIEEgdG8gQi4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBBIGFuZCBCICgxICZsZTsgQSwgQiAmbHQ7IDEwMDAsIEEgJm5lOyBCKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgNSkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWluIHRoZSBwcmVkZWZpbmVkIGZyZXF1ZW5jaWVzIChvbmUgaW50ZWdlciBwZXIgbGluZSwgZWFjaCBsZXNzIHRoYW4gMTAwMCkuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgYnV0dG9uIHByZXNzZXMgbmVlZGVkIHRvIGNoYW5nZSB0aGUgZnJlcXVlbmN5IGZyb20gQSB0byBCLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==