증가 수열
시간 제한1초메모리 제한1024 MB
각 테스트 케이스에서 b[i]가 a[i]와 다르면서 순증가하는 양의 정수 수열 b를 만들고, 마지막 원소 b[n]의 최솟값을 구한다.
문제
수열 이 주어진다. 다음 조건을 만족하는 수열 을 좋은 수열이라고 정의한다:
- 는 양의 정수이다().
- 이다().
- 이다.
좋은 수열 에 대하여, 의 최솟값을 구하여라.
입력
각 입력은 여러 개의 테스트 케이스로 이루어져 있다. 첫 번째 줄에 테스트 케이스의 개수 가 주어진다(). 다음 줄부터 각각의 테스트 케이스가 주어진다.
각각의 테스트 케이스의 첫 번째 줄에 정수 이 주어진다 ().
두 번째 줄에 개의 정수 이 공백으로 구분되어 주어진다 ().
출력
각각의 테스트 케이스마다 정답을 출력한다.
힌트
첫 번째 테스트 케이스에서, 은 좋은 수열이다. 인 좋은 수열 가 없음을 증명할 수 있다.
두 번째 테스트 케이스에서, 가 가능하다.
세 번째 테스트 케이스에서, 가 가능하다.