특별한 게임
시간 제한1초메모리 제한512 MB
Dmytryk와 Petro가 1부터 2n까지 카드로 n라운드 게임을 할 때, 최적으로 플레이하면 Dmytryk가 이길 수 있는 최대 라운드 수를 구합니다.
문제
드미트릭과 페트로가 다음 게임을 한다. 값이 1부터 까지의 정수인 카드 장이 있으며, 모든 값은 서로 다르다. 게임을 시작할 때 각 플레이어는 정확히 장의 카드를 가진다.
전체 라운드가 진행되며, 첫 라운드의 선공은 드미트릭이다. 각 라운드에서 선공 플레이어는 자신의 카드 한 장을 낸다. 그다음 후공 플레이어가 선공의 카드를 보고 자신의 카드 한 장을 낸다. 값이 더 큰 카드를 낸 플레이어가 그 라운드에서 이기고, 다음 라운드의 선공이 된다. 그 뒤 두 카드는 게임에서 제외된다.
추가 규칙이 하나 있다. 각 라운드에서 후공 플레이어가 상대가 낸 카드보다 값이 큰 카드를 가지고 있다면, 그런 카드 중 한 장을 반드시 내야 한다.
각 플레이어의 목표는 자신이 이기는 라운드 수를 최대화하는 것이다. 두 플레이어가 최선을 다할 때 드미트릭이 이길 수 있는 라운드 수의 최댓값을 구하시오.
입력
첫 줄에 정수 ()이 주어진다. 둘째 줄에는 드미트릭의 카드 개가, 셋째 줄에는 페트로의 카드 개가 주어진다.
출력
문제의 답을 출력한다.