문제
경주 연습을 하는 다오
다오는 경주 대회를 열기 위해 $N$개의 트랙을 준비했다. $i$번째로 경주하는 트랙의 길이는 $A_i$이다.
관중들은 트랙의 길이가 점점 길어져야 경주가 재미있다고 생각한다. 즉, $A_1<A_2<\cdots <A_N$인 경우 경주가 재미있다고 생각한다. 이를 위해 다오는 다음과 같은 시행을 0회 이상 할 수 있다.
- 1ドル\le i\le N$인 $i$를 고른 뒤, $i$번째 트랙의 길이를 $K$만큼 늘린다. 즉, $A_i$를 $A_i+K$로 바꾼다.
- 위 시행은 각 $i$에 대해 최대 한 번만 할 수 있다.
다오가 트랙의 길이를 점점 증가하도록 만들 수 있는지 판단하고, 만약 가능하다면 이를 위해 필요한 시행의 최소 횟수를 구하시오.
출력
만약 다오가 트랙의 길이를 점점 증가하도록 만들 수 있다면, 이를 위해 필요한 최소 시행의 횟수를 출력하여라.
만약 다오가 트랙의 길이를 점점 증가하도록 만들 수 없다면, -1을 출력하여라.
제한
- 1ドル\le N\le 10^5$
- 1ドル\le K\le 10^9$
- 0ドル\le A_i\le 10^9$
서브태스크
| 번호 | 배점 | 제한 | | 1 | 10 | $N \le 3$
|
| 2 | 30 | $N \le 10$
|
| 3 | 60 | 문제에 주어진 조건 이외에 추가 제한 조건이 없다.
|
2번과 3번 트랙의 길이를 2ドル$만큼 늘리면 각 트랙의 길이는 $A=[4, 5, 6]$이 되어 트랙의 길이가 점점 길어진다.
트랙의 길이가 점점 증가하도록 트랙의 길이를 늘리는 방법이 존재하지 않는다.
3번, 5번, 6번 트랙의 길이를 5ドル$만큼 늘리면 각 트랙의 길이는 $A=[2, 4, 8, 9, 10, 13]$이 되어 트랙의 길이가 점점 길어진다.
W3sicHJvYmxlbV9pZCI6IjMxMDY3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViMmU0XHVjNjI0XHVjNzU4IFx1YWNiZFx1YzhmYyBcdWIzMDBcdWQ2OGMiLCJkZXNjcmlwdGlvbiI6IjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3UuYWNtaWNwYy5uZXRcLzZhNmFiY2IwLThiNTgtNDY0Mi1iODllLTAxNGJhZjViNzcxM1wva2FydHJpZGVyLmpwZ1wiIHN0eWxlPVwiaGVpZ2h0OiAzMDRweDsgd2lkdGg6IDU0MHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5cdWFjYmRcdWM4ZmMgXHVjNWYwXHVjMmI1XHVjNzQ0IFx1ZDU1OFx1YjI5NCBcdWIyZTRcdWM2MjQ8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNjI0XHViMjk0IFx1YWNiZFx1YzhmYyBcdWIzMDBcdWQ2OGNcdWI5N2MgXHVjNWY0XHVhZTMwIFx1YzcwNFx1ZDU3NCAkTiRcdWFjMWNcdWM3NTggXHVkMmI4XHViNzk5XHVjNzQ0IFx1YzkwMFx1YmU0NFx1ZDU4OFx1YjJlNC4gJGkkXHViYzg4XHVjOWY4XHViODVjIFx1YWNiZFx1YzhmY1x1ZDU1OFx1YjI5NCBcdWQyYjhcdWI3OTlcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0ICRBX2kkXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkMDBcdWM5MTFcdWI0ZTRcdWM3NDAgXHVkMmI4XHViNzk5XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWM4MTBcdWM4MTAgXHVhZTM4XHVjNWI0XHVjODM4XHVjNTdjIFx1YWNiZFx1YzhmY1x1YWMwMCBcdWM3YWNcdWJiZjhcdWM3ODhcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTVjXHViMmU0LiBcdWM5ODksICRBXzEmbHQ7QV8yJmx0O1xcY2RvdHMgJmx0O0FfTiRcdWM3NzggXHVhY2JkXHVjNmIwIFx1YWNiZFx1YzhmY1x1YWMwMCBcdWM3YWNcdWJiZjhcdWM3ODhcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI5N2MgXHVjNzA0XHVkNTc0IFx1YjJlNFx1YzYyNFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzJkY1x1ZDU4OVx1Yzc0NCAwXHVkNjhjIFx1Yzc3NFx1YzBjMSBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kMVxcbGUgaVxcbGUgTiRcdWM3NzggJGkkXHViOTdjIFx1YWNlMFx1Yjk3OCBcdWI0YTQsICRpJFx1YmM4OFx1YzlmOCBcdWQyYjhcdWI3OTlcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjICRLJFx1YjljY1x1ZDA3YyBcdWIyOThcdWI5YjBcdWIyZTQuIFx1Yzk4OSwgJEFfaSRcdWI5N2MgJEFfaStLJFx1Yjg1YyBcdWJjMTRcdWFmYmNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzcwNCBcdWMyZGNcdWQ1ODlcdWM3NDAgXHVhYzAxICRpJFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjZDVjXHViMzAwIFx1ZDU1YyBcdWJjODhcdWI5Y2MgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViMmU0XHVjNjI0XHVhYzAwIFx1ZDJiOFx1Yjc5OVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjODEwXHVjODEwIFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWQzMTBcdWIyZThcdWQ1NThcdWFjZTAsIFx1YjljY1x1YzU3ZCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTRcdWJhNzQgXHVjNzc0XHViOTdjIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjMmRjXHVkNTg5XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWQ2OWZcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQyYjhcdWI3OTlcdWM3NTggXHVjMjE4ICROJFx1YWNmYyBcdWQyYjhcdWI3OTlcdWM3NDQgXHViMjk4XHViOWI0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhZTM4XHVjNzc0ICRLJFx1YWMwMCBcdWI3NDRcdWM1YjRcdWM0ZjBcdWFlMzBcdWI5N2MgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWQyYjhcdWI3OTlcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMTggJEFfMSQsICRBXzIkLCAkXFxjZG90cyQsICRBX04kXHVjNzc0IFx1Yjc0NFx1YzViNFx1YzRmMFx1YWUzMFx1Yjk3YyBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWI5Y2NcdWM1N2QgXHViMmU0XHVjNjI0XHVhYzAwIFx1ZDJiOFx1Yjc5OVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjODEwXHVjODEwIFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHVjNzc0XHViOTdjIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YzJkY1x1ZDU4OVx1Yzc1OCBcdWQ2OWZcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QgXHViMmU0XHVjNjI0XHVhYzAwIFx1ZDJiOFx1Yjc5OVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjODEwXHVjODEwIFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YmE3NCwgPGNvZGU+LTE8XC9jb2RlPlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPiQxXFxsZSBOXFxsZSAxMF41JDxcL2xpPlxyXG5cdDxsaT4kMVxcbGUgS1xcbGUgMTBeOSQ8XC9saT5cclxuXHQ8bGk+JDBcXGxlIEFfaVxcbGUgMTBeOSQ8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2sxIjoiPHA+JE4gXFxsZSAzJDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+JE4gXFxsZSAxMCQ8XC9wPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPlx1YmIzOFx1YzgxY1x1YzVkMCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjODcwXHVhYzc0IFx1Yzc3NFx1YzY3OFx1YzVkMCBcdWNkOTRcdWFjMDAgXHVjODFjXHVkNTVjIFx1Yzg3MFx1YWM3NFx1Yzc3NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPjJcdWJjODhcdWFjZmMgM1x1YmM4OCBcdWQyYjhcdWI3OTlcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjICQyJFx1YjljY1x1ZDA3YyBcdWIyOThcdWI5YWNcdWJhNzQgXHVhYzAxIFx1ZDJiOFx1Yjc5OVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgJEE9WzQsIDUsIDZdJFx1Yzc3NCBcdWI0MThcdWM1YjQgXHVkMmI4XHViNzk5XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWM4MTBcdWM4MTAgXHVhZTM4XHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzIiOiI8cD5cdWQyYjhcdWI3OTlcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIFx1YzgxMFx1YzgxMCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIzYzRcdWI4NWQgXHVkMmI4XHViNzk5XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWIyOThcdWI5YWNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMyI6IjxwPjNcdWJjODgsIDVcdWJjODgsIDZcdWJjODggXHVkMmI4XHViNzk5XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyAkNSRcdWI5Y2NcdWQwN2MgXHViMjk4XHViOWFjXHViYTc0IFx1YWMwMSBcdWQyYjhcdWI3OTlcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0ICRBPVsyLCA0LCA4LCA5LCAxMCwgMTNdJFx1Yzc3NCBcdWI0MThcdWM1YjQgXHVkMmI4XHViNzk5XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWM4MTBcdWM4MTAgXHVhZTM4XHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjMxMDY3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRGFvJ3MgUmFjaW5nIENvbXBldGl0aW9uIiwiZGVzY3JpcHRpb24iOiI8cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91LmFjbWljcGMubmV0XC82YTZhYmNiMC04YjU4LTQ2NDItYjg5ZS0wMTRiYWY1Yjc3MTNcL2thcnRyaWRlci5qcGdcIiBzdHlsZT1cImhlaWdodDogMzA0cHg7IHdpZHRoOiA1NDBweDtcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+RGFvLCBwcmFjdGljaW5nIGZvciBoaXMgcmFjZTxcL3A+XHJcblxyXG48cD5EYW8gcHJlcGFyZWQgJE4kIHJhY2luZyB0cmFja3MgdG8gaG9sZCBhIHJhY2luZyBjb21wZXRpdGlvbi4gVGhlIGxlbmd0aCBvZiB0aGUgJGkkLXRoIHJhY2luZyB0cmFjayBpcyAkQV9pJC48XC9wPlxyXG5cclxuPHA+VGhlIHNwZWN0YXRvcnMgdGhpbmsgdGhlIGNvbXBldGl0aW9uIGlzIGZ1biB3aGVuIHRoZSBsZW5ndGhzIG9mIHRoZSB0cmFja3MgaW5jcmVtZW50YWxseSBpbmNyZWFzZS4gSW4gb3RoZXIgd29yZHMsIGlmIHRoZSBjb25kaXRpb24gJEFfMSZsdDtBXzImbHQ7XFxjZG90cyAmbHQ7QV9OJCBpcyBzYXRpc2ZpZWQsIHRoZSBzcGVjdGF0b3JzIGNvbnNpZGVyIHRoZSBjb21wZXRpdGlvbiBmdW4uIFRvIG1lZXQgdGhpcyBjb25kaXRpb24sIERhbyBjYW4gYXBwbHkgdGhlIGZvbGxvd2luZyBvcGVyYXRpb24gYW55IG51bWJlciBvZiB0aW1lcyAocG9zc2libHkgemVybyk6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+c2VsZWN0IGFuIGluZGV4ICRpJCBzdWNoIHRoYXQgJDFcXGxlIGlcXGxlIE4kIGhvbGRzLCBhbmQgaW5jcmVhc2UgdGhlIGxlbmd0aCBvZiB0aGUgJGkkLXRoIHRyYWNrIGJ5ICRLJC4gSW4gb3RoZXIgd29yZHMsIHJlcGxhY2UgJEFfaSQgYnkgJEFfaStLJC48XC9saT5cclxuXHQ8bGk+RGFvIGNhbiBhcHBseSB0aGUgb3BlcmF0aW9uIGFib3ZlIGF0IG1vc3Qgb25jZSBmb3IgZWFjaCAkaSQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+RGV0ZXJtaW5lIGlmIERhbyBjYW4gaW5jcmVtZW50YWxseSBpbmNyZWFzZSB0aGUgbGVuZ3RoIG9mIHRoZSB0cmFjaywgYW5kIGlmIHNvLCBmaW5kIHRoZSBtaW5pbXVtIG51bWJlciBvZiBvcGVyYXRpb25zIHJlcXVpcmVkIHRvIGRvIHNvLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzICROJCBhbmQgJEskICZtZGFzaDsgdGhlIG51bWJlciBvZiB0cmFja3MgYW5kIHRoZSBsZW5ndGggdGhhdCBEYW8gY2FuIGluY3JlYXNlIGZvciBlYWNoIHRyYWNrLCBzZXBhcmF0ZWQgYnkgYSBzcGFjZS48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIGludGVnZXJzICRBXzEkLCAkQV8yJCwgJFxcY2RvdHMkLCAkQV9OJCBkZW5vdGluZyB0aGUgbGVuZ3RoIG9mIGVhY2ggdHJhY2ssIHNlcGFyYXRlZCBieSBhIHNwYWNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPklmIERhbyBjYW4gaW5jcmVtZW50YWxseSBpbmNyZWFzZSB0aGUgbGVuZ3RocyBvZiB0aGUgdHJhY2tzLCBwcmludCB0aGUgbWluaW11bSBudW1iZXIgb2Ygb3BlcmF0aW9ucyByZXF1aXJlZCBmb3IgRGFvLjxcL3A+XHJcblxyXG48cD5JZiBEYW8gY2Fubm90IG1ha2UgdGhlIGxlbmd0aHMgb2YgdGhlIHRyYWNrcyBpbmNyZW1lbnRhbGx5IGluY3JlYXNlLCBwcmludCA8Y29kZT4tMTxcL2NvZGU+LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDFcXGxlIE5cXGxlIDEwXjUkPFwvbGk+XHJcblx0PGxpPiQxXFxsZSBLXFxsZSAxMF45JDxcL2xpPlxyXG5cdDxsaT4kMFxcbGUgQV9pXFxsZSAxMF45JDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kTiBcXGxlIDMkPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD4kTiBcXGxlIDEwJDxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+VGhlcmUgYXJlIG5vIGFkZGl0aW9uYWwgY29uc3RyYWludHMuPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPklmIHlvdSBpbmNyZWFzZSB0aGUgc2Vjb25kIGFuZCB0aGlyZCB0cmFjayBsZW5ndGhzIGJ5ICQyJCwgdGhlIGxlbmd0aHMgb2YgZWFjaCB0cmFjayBiZWNvbWUgJEE9WzQsNSw2XSQsIHdoaWNoIGFyZSBpbmNyZW1lbnRhbGx5IGluY3JlYXNpbmcuPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPlRoZXJlIGlzIG5vIHdheSB0byBpbmNyZWFzZSZuYnNwO2xlbmd0aHMgb2YgdHJhY2tzJm5ic3A7c28gdGhhdCB0aGV5IGFyZSBpbmNyZW1lbnRhbGx5IGluY3JlYXNpbmcuPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMyI6IjxwPklmIHlvdSBpbmNyZWFzZSB0aGUgbGVuZ3RocyBvZiB0aGUgdGhpcmQsIGZpZnRoLCBhbmQgc2l4dGggdHJhY2tzIGJ5ICQ1JCwgdGhlIGxlbmd0aHMgb2YgZWFjaCB0cmFjayBiZWNvbWUgJEE9WzIsNCw4LDksMTAsMTNdJCwgd2hpY2ggYXJlIGluY3JlbWVudGFsbHkgaW5jcmVhc2luZy48XC9wPlxyXG4ifV0=