문제
서울과학고의 자료구조 수업은 $N$명의 학생이 수강한다. 자료구조 수업은 중간고사와 기말고사가 존재하며, 각 시험의 점수는 0ドル$ 이상 10ドル^6$ 이하의 정수이다.
선생님은 학생들의 시험 점수를 바탕으로 학생들에게 '상', '중', '하' 중 하나의 등급을 부여하려고 한다. 이때 부여하는 등급은 다음 두 조건에 맞아야 한다.
- 각 등급은 적어도 한 명의 학생이 받아야 한다.
- 더 높은 등급을 받은 학생은 더 낮은 등급을 받은 학생보다 중간고사, 기말고사 점수가 모두 더 높아야 한다.
선생님은 불균형도를 최소화하도록 등급을 매기고자 한다. '상', '중', '하' 등급을 받은 사람의 수를 각각 $a,ドル $b,ドル $c$라고 하자. 이때 불균형도는 $\max(a,b,c) -\min(a,b,c)$로 정의된다.
가능한 불균형도의 최솟값을 구하여라.
출력
가능한 불균형도의 최솟값을 출력한다.
만약 선생님이 조건에 맞게 등급을 부여하는 것이 불가능하다면, -1을 출력한다.
제한
- 3ドル\le N\le 2\times 10^5$
- 0ドル\le A_i,B_i\le 10^6$ $(1\le i\le N)$
- 입력에 주어지는 모든 수는 정수이다.
서브태스크
| 번호 | 배점 | 제한 | | 1 | 10 | $N \le 80$
|
| 2 | 20 | $N \le 600$
|
| 3 | 30 | $N \le 3\ 000$
|
| 4 | 40 | 추가 제한 조건이 없다.
|
노트
$\max(a,b,c)$와 $\min(a,b,c)$는 각각 $a,ドル $b,ドル $c$ 중 최댓값과 최솟값을 의미한다.
W3sicHJvYmxlbV9pZCI6IjMxMDY4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhZGUwXHVkNjE1IFx1YzdhMVx1ZDc4YyBcdWI0ZjFcdWFlMDkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzExY1x1YzZiOFx1YWNmY1x1ZDU1OVx1YWNlMFx1Yzc1OCBcdWM3OTBcdWI4Y2NcdWFkNmNcdWM4NzAgXHVjMjE4XHVjNWM1XHVjNzQwICROJFx1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVjMjE4XHVhYzE1XHVkNTVjXHViMmU0LiBcdWM3OTBcdWI4Y2NcdWFkNmNcdWM4NzAgXHVjMjE4XHVjNWM1XHVjNzQwIFx1YzkxMVx1YWMwNFx1YWNlMFx1YzBhY1x1YzY0MCBcdWFlMzBcdWI5ZDBcdWFjZTBcdWMwYWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHViYTcwLCBcdWFjMDEgXHVjMmRjXHVkNWQ4XHVjNzU4IFx1YzgxMFx1YzIxOFx1YjI5NCAkMCQgXHVjNzc0XHVjMGMxICQxMF42JCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMjBcdWMwZGRcdWIyZDhcdWM3NDAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzU4IFx1YzJkY1x1ZDVkOCBcdWM4MTBcdWMyMThcdWI5N2MgXHViYzE0XHVkMGQ1XHVjNzNjXHViODVjIFx1ZDU1OVx1YzBkZFx1YjRlNFx1YzVkMFx1YWM4YyAmIzM5O1x1YzBjMSYjMzk7LCAmIzM5O1x1YzkxMSYjMzk7LCAmIzM5O1x1ZDU1OCYjMzk7IFx1YzkxMSBcdWQ1NThcdWIwOThcdWM3NTggXHViNGYxXHVhZTA5XHVjNzQ0IFx1YmQ4MFx1YzVlY1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YyBcdWJkODBcdWM1ZWNcdWQ1NThcdWIyOTQgXHViNGYxXHVhZTA5XHVjNzQwIFx1YjJlNFx1Yzc0YyBcdWI0NTAgXHVjODcwXHVhYzc0XHVjNWQwIFx1YjlkZVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVhYzAxIFx1YjRmMVx1YWUwOVx1Yzc0MCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTVjIFx1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHViYzFiXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViMzU0IFx1YjE5Mlx1Yzc0MCBcdWI0ZjFcdWFlMDlcdWM3NDQgXHViYzFiXHVjNzQwIFx1ZDU1OVx1YzBkZFx1Yzc0MCBcdWIzNTQgXHViMGFlXHVjNzQwIFx1YjRmMVx1YWUwOVx1Yzc0NCBcdWJjMWJcdWM3NDAgXHVkNTU5XHVjMGRkXHViY2Y0XHViMmU0IFx1YzkxMVx1YWMwNFx1YWNlMFx1YzBhYywgXHVhZTMwXHViOWQwXHVhY2UwXHVjMGFjIFx1YzgxMFx1YzIxOFx1YWMwMCBcdWJhYThcdWI0NTAgXHViMzU0IFx1YjE5Mlx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjMTIwXHVjMGRkXHViMmQ4XHVjNzQwIDxzdHJvbmc+XHViZDg4XHVhZGUwXHVkNjE1XHViM2M0PFwvc3Ryb25nPlx1Yjk3YyBcdWNkNWNcdWMxOGNcdWQ2NTRcdWQ1NThcdWIzYzRcdWI4NWQgXHViNGYxXHVhZTA5XHVjNzQ0IFx1YjllNFx1YWUzMFx1YWNlMFx1Yzc5MCBcdWQ1NWNcdWIyZTQuICYjMzk7XHVjMGMxJiMzOTssICYjMzk7XHVjOTExJiMzOTssICYjMzk7XHVkNTU4JiMzOTsgXHViNGYxXHVhZTA5XHVjNzQ0IFx1YmMxYlx1Yzc0MCBcdWMwYWNcdWI3OGNcdWM3NTggXHVjMjE4XHViOTdjIFx1YWMwMVx1YWMwMSAkYSQsICRiJCwgJGMkXHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0XHViNTRjIFx1YmQ4OFx1YWRlMFx1ZDYxNVx1YjNjNFx1YjI5NCAkXFxtYXgoYSxiLGMpIC1cXG1pbihhLGIsYykkXHViODVjIFx1YzgxNVx1Yzc1OFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAwXHViMmE1XHVkNTVjIFx1YmQ4OFx1YWRlMFx1ZDYxNVx1YjNjNFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWQ1NTlcdWMwZGRcdWM3NTggXHVjMjE4ICROJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOCBcdWI0YTQgJE4kXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjRlNCBcdWM5MTEgJGkkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAkaSRcdWJjODggXHVkNTU5XHVjMGRkXHVjNzU4IFx1YzkxMVx1YWMwNFx1YWNlMFx1YzBhY1x1YzY0MCBcdWFlMzBcdWI5ZDBcdWFjZTBcdWMwYWMgXHVjODEwXHVjMjE4ICRBX2kkXHVjNjQwICRCX2kkXHVhYzAwIFx1Yjc0NFx1YzViNFx1YzRmMFx1YWUzMFx1Yjk3YyBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDBcdWIyYTVcdWQ1NWMgXHViZDg4XHVhZGUwXHVkNjE1XHViM2M0XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCBcdWMxMjBcdWMwZGRcdWIyZDhcdWM3NzQgXHVjODcwXHVhYzc0XHVjNWQwIFx1YjlkZVx1YWM4YyBcdWI0ZjFcdWFlMDlcdWM3NDQgXHViZDgwXHVjNWVjXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTRcdWJhNzQsIDxjb2RlPi0xPFwvY29kZT5cdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD4kXFxtYXgoYSxiLGMpJFx1YzY0MCAkXFxtaW4oYSxiLGMpJFx1YjI5NCBcdWFjMDFcdWFjMDEgJGEkLCAkYiQsICRjJCBcdWM5MTEgXHVjZDVjXHViMzEzXHVhYzEyXHVhY2ZjIFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDNcXGxlIE5cXGxlIDJcXHRpbWVzIDEwXjUkPFwvbGk+XHJcblx0PGxpPiQwXFxsZSBBX2ksQl9pXFxsZSAxMF42JCAkKDFcXGxlIGlcXGxlIE4pJDxcL2xpPlxyXG5cdDxsaT5cdWM3ODVcdWI4MjVcdWM1ZDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YmFhOFx1YjRlMCBcdWMyMThcdWIyOTQgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kTiBcXGxlIDgwJDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+JE4gXFxsZSA2MDAkPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD4kTiBcXGxlIDNcXCAwMDAkPFwvcD5cclxuIiwic3VidGFzazQiOiI8cD5cdWNkOTRcdWFjMDAgXHVjODFjXHVkNTVjIFx1Yzg3MFx1YWM3NFx1Yzc3NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMzEwNjgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCYWxhbmNlZCBHcmFkZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkF0IFNlb3VsIFNjaWVuY2UgSGlnaCBTY2hvb2woU1NIUyksICROJCBzdHVkZW50cyB0YWtlIHRoZSBkYXRhIHN0cnVjdHVyZSBjb3Vyc2UuIFRoZSBjb3Vyc2UgaGFzIG1pZHRlcm0gYW5kIGZpbmFsIGV4YW1zLCBhbmQgdGhlIHNjb3JlcyBmb3IgZWFjaCBleGFtIGFyZSBpbnRlZ2VycyBiZXR3ZWVuICQwJCBhbmQgJDEwXjYkLCBpbmNsdXNpdmUuPFwvcD5cclxuXHJcbjxwPlRoZSB0ZWFjaGVyIHdhbnRzIHRvIGdpdmUgZWFjaCBzdHVkZW50IGdvb2QsIGZhaXIsIGFuZCBwb29yIGdyYWRlcyBiYXNlZCBvbiB0aGVpciB0ZXN0IHNjb3Jlcy4gVGhlIGdyYWRlcyBtdXN0IHNhdGlzZnkgdGhlIGZvbGxvd2luZyB0d28gY29uZGl0aW9uczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5FYWNoIGdyYWRlIHNob3VsZCBiZSBnaXZlbiB0byBhdCBsZWFzdCBvbmUgb2YgdGhlIHN0dWRlbnRzLjxcL2xpPlxyXG5cdDxsaT5TdHVkZW50cyB3aG8gcmVjZWl2ZWQgaGlnaGVyIGdyYWRlcyBzaG91bGQgaGF2ZSBib3RoIGhpZ2hlciBtaWR0ZXJtIGFuZCBmaW5hbCBzY29yZXMgdGhhbiB0aG9zZSB3aG8gcmVjZWl2ZWQgbG93ZXIgZ3JhZGVzLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZSB0ZWFjaGVyIHdhbnRzIHRvIG1pbmltaXplIDxzdHJvbmc+aW1iYWxhbmNlPFwvc3Ryb25nPi4gTGV0ICRhJCwgJGIkLCBhbmQgJGMkIGJlIHRoZSBudW1iZXIgb2Ygc3R1ZGVudHMgd2hvIHJlY2VpdmVkIGdvb2QsIGZhaXIsIGFuZCBwb29yIGdyYWRlcywgcmVzcGVjdGl2ZWx5LiBUaGUgaW1iYWxhbmNlIGlzIGRlZmluZWQgYXMgJFxcbWF4KGEsYixjKSAtXFxtaW4oYSxiLGMpJC48XC9wPlxyXG5cclxuPHA+RmluZCB0aGUgbWluaW11bSBwb3NzaWJsZSB2YWx1ZSBvZiBpbWJhbGFuY2UuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyICROJCAmbWRhc2g7IHRoZSBudW1iZXIgb2Ygc3R1ZGVudHMuPFwvcD5cclxuXHJcbjxwPlRoZW4sICROJCBsaW5lcyBmb2xsb3cuIFRoZSAkaSQtdGggb2YgdGhlbSBjb250YWlucyB0d28gaW50ZWdlcnMgJEFfaSQgYW5kICRCX2kkLCB0aGUgbWlkdGVybSBhbmQgZmluYWwgc2NvcmVzIG9mICRpJC10aCBzdHVkZW50cywgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgdGhlIG1pbmltdW0gcG9zc2libGUgdmFsdWUgb2YgaW1iYWxhbmNlLjxcL3A+XHJcblxyXG48cD5JZiBpdCBpcyBpbXBvc3NpYmxlIGZvciB0aGUgdGVhY2hlciB0byBncmFkZSB0aGUgc3R1ZGVudHMgc2F0aXNmeWluZyB0aGUgY29uZGl0aW9ucyBhYm92ZSwgcHJpbnQgPGNvZGU+LTE8XC9jb2RlPi48XC9wPlxyXG4iLCJoaW50IjoiPHA+JFxcbWF4KGEsYixjKSQgYW5kICRcXG1pbihhLGIsYykkIG1lYW5zIHRoZSBtYXhpbXVtIGFuZCBtaW5pbXVtIHZhbHVlIGFtb25nICRhJCwgJGIkLCBhbmQgJGMkLCByZXNwZWN0aXZlbHkuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPiQzXFxsZSBOXFxsZSAyXFx0aW1lcyAxMF41JDxcL2xpPlxyXG5cdDxsaT4kMFxcbGUgQV9pLEJfaVxcbGUgMTBeNiQgJCgxXFxsZSBpXFxsZSBOKSQ8XC9saT5cclxuXHQ8bGk+QWxsIG51bWJlcnMgaW4gdGhlIGlucHV0IGFyZSBpbnRlZ2Vycy48XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2sxIjoiPHA+JE4gXFxsZSA4MCQ8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPiROIFxcbGUgNjAwJDxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+JE4gXFxsZSAzXFwgMDAwJDxcL3A+XHJcbiIsInN1YnRhc2s0IjoiPHA+VGhlcmUgYXJlIG5vIGFkZGl0aW9uYWwgY29uc3RyYWludHMuPFwvcD5cclxuIn1d