시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 364 235 216 66.873%

문제

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

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

  • 첫 번째 버튼은 주파수를 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+XHJcblx0PGxpPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHViYzg0XHVkMmJjXHVjNzQwIFx1YzhmY1x1ZDMwY1x1YzIxOFx1Yjk3YyAxTUh6IFx1Yzk5ZFx1YWMwMFx1YzJkY1x1ZDBhOFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWJjODRcdWQyYmNcdWM3NDAgXHVjOGZjXHVkMzBjXHVjMjE4XHViOTdjIDFNSHogXHVhYzEwXHVjMThjXHVjMmRjXHVkMGE4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWIwOThcdWJhMzhcdWM5YzAgTlx1YWMxY1x1Yzc1OCBcdWJjODRcdWQyYmNcdWM3NDAgXHVjOTkwXHVhY2E4XHVjYzNlXHVhZTMwIFx1YWUzMFx1YjJhNVx1YzczY1x1Yjg1YywgXHViYmY4XHViOWFjIFx1YzljMFx1YzgxNVx1YjQxYyBcdWM4ZmNcdWQzMGNcdWMyMThcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzkwMFx1ZDU1OFx1YjI5NCBcdWJhYjhcdWM3NzQgXHVjNTQ4XHVjODhiXHVjNTQ0Jm5ic3A7XHVkNTU4XHViOGU4XHVjNWQwIFx1YzE5MFx1YWMwMFx1Yjc3ZFx1Yzc0NCBcdWJhODcmbmJzcDtcdWJjODggXHVjNmMwXHVjOWMxXHVjNzc0XHVjOWMwIFx1YmFiYlx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjNmIwXHViOWFjXHVjNzU4IFx1YjNjNFx1YzZjMFx1Yzc3NCBcdWQ1NDRcdWM2OTRcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDYwNFx1YzdhYyZuYnNwO1x1YzhmY1x1ZDMwY1x1YzIxOCBBXHVjNjQwIFx1YjRlM1x1YWNlMFx1YzJmNlx1Yzc0MCBcdWM4ZmNcdWQzMGNcdWMyMTggQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM4ZmNcdWQzMGNcdWMyMTggQVx1YzVkMFx1YzExYyBCXHViODVjIFx1YWMwOCBcdWI1NGMgXHViMjBjXHViN2VjXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjODAxXHVjNzQwIFx1YmM4NFx1ZDJiY1x1YzIxOFx1Yjk3YyZuYnNwO1x1YWQ2Y1x1ZDU3NFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiZuYnNwO1x1YzkwNFx1YzVkNCBcdWM4MTVcdWMyMTgmbmJzcDtBXHVjNjQwIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0ICgxICZsZTsgQSwgQiAmbHQ7IDEwMDAsIEEgJm5lOyBCKS48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjJm5ic3A7XHVjOTA0XHVjNWQ0IFx1YzgxNVx1YzIxOCZuYnNwO05cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0ICgxICZsZTsgTiAmbGU7IDUpLjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDQgXHViYmY4XHViOWFjIFx1YzljMFx1YzgxNVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjOGZjXHVkMzBjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCZuYnNwOyhcdWM4ZmNcdWQzMGNcdWMyMThcdWIyOTQmbmJzcDsxMDAwIFx1YmNmNFx1YjJlNCBcdWM3OTFcdWIyZTQpLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzhmY1x1ZDMwY1x1YzIxOCBBXHVjNWQwXHVjMTFjIEJcdWI4NWMgXHVhYzA4IFx1YjU0YyBcdWIyMGNcdWI3ZWNcdWM1N2MgXHVkNTU4XHViMjk0IFx1YmM4NFx1ZDJiY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxMzUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSQURJTyIsImRlc2NyaXB0aW9uIjoiPHA+U2xhdmtvIGlzIGRyaXZpbmcgaGlzIG5ldyBLYXJhbWJvbCBHVDIwIGNhciB3aXRoIGEgdG9wLW9mLXRoZS1saW5lIHJhZGlvICh3aGljaCwgb2YgY291cnNlLCBTbGF2a28gbWFkZSBoaW1zZWxmIGluIGhpcyBiYXNlbWVudCwgbmV4dCB0byB0aGUgbGF1bmRyeSB3YXNoZXIpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5TbGF2a28mIzM5O3MgcmFkaW8gaXMgdmVyeSBoaS10ZWNoIGFuZCBpcyBlcXVpcHBlZCB3aXRoIHR3byBidXR0b25zIHRoYXQgYXJlIHVzZWQgdG8gbWFudWFsbHkgY2hhbmdlIHRoZSBmcmVxdWVuY3ksIGFuZCBzZXZlcmFsIGJ1dHRvbnMgdGhhdCBjaGFuZ2UgdGhlIGZyZXF1ZW5jeSB0byBvbmUgb2YgdGhlIHByZWRlZmluZWQgZnJlcXVlbmNpZXMuIE1vcmUgcHJlY2lzZWx5OiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSBmaXJzdCBidXR0b24gaW5jcmVhc2VzIHRoZSBmcmVxdWVuY3kgYnkgMSAob25lKSBNSHo7Jm5ic3A7PFwvbGk+XHJcblx0PGxpPlRoZSBzZWNvbmQgYnV0dG9uIGRlY3JlYXNlcyB0aGUgZnJlcXVlbmN5IGJ5IDEgKG9uZSkgTUh6OyZuYnNwOzxcL2xpPlxyXG5cdDxsaT5FYWNoIG9mIHRoZSByZW1haW5pbmcgTiBidXR0b25zIGNoYW5nZXMgdGhlIGZyZXF1ZW5jeSB0byBvbmUgb2YgdGhlIE4gcHJlZGVmaW5lZCBmcmVxdWVuY2llcy48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Zb3VyIGpvYiBpcyB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gdHdvIGZyZXF1ZW5jaWVzIEEgYW5kIEIsIGNvbXB1dGVzIHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgYnV0dG9uIHByZXNzZXMgbmVlZGVkIHRvIGNoYW5nZSB0aGUgZnJlcXVlbmN5IGZyb20gQSB0byBCLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIEEgYW5kIEIgKDEgJmxlOyBBLCBCICZsdDsgMTAwMCwgQSAmbmU7IEIpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyA1KS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW4gdGhlIHByZWRlZmluZWQgZnJlcXVlbmNpZXMgKG9uZSBpbnRlZ2VyIHBlciBsaW5lLCBlYWNoIGxlc3MgdGhhbiAxMDAwKS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBidXR0b24gcHJlc3NlcyBuZWVkZWQgdG8gY2hhbmdlIHRoZSBmcmVxdWVuY3kgZnJvbSBBIHRvIEIuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d