증가 수열
면접 대비시간 제한1초메모리 제한1024 MB
양의 정수 수열 a가 주어질 때, 각 b_i가 a_i와 다르면서 엄격히 증가하는 수열의 마지막 값 b_n의 최솟값을 구합니다.
문제
수열 이 주어진다. 다음 조건을 만족하는 수열 을 좋은 수열이라고 정의한다:
- 는 양의 정수이다().
- 이다().
- 이다.
좋은 수열 중에서 의 최솟값을 구하라.
입력
각 입력은 여러 개의 테스트 케이스로 이루어진다. 첫 번째 줄에 테스트 케이스의 개수 가 주어진다(). 다음 줄부터 각각의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에 정수 이 주어진다().
두 번째 줄에 개의 정수 이 공백으로 구분되어 주어진다().
출력
각 테스트 케이스마다 정답을 출력한다.
힌트
첫 번째 테스트 케이스에서 은 좋은 수열이다. 인 좋은 수열 가 없음을 증명할 수 있다. 두 번째 테스트 케이스에서는 가 가능하다. 세 번째 테스트 케이스에서는 가 가능하다.