다다스의 라면 먹방

다다스는 $N$개의 라면을 차례로 먹으려고 한다. $i$번 라면을 완전히 끓이는 데에는 $A_i$만큼의 시간이 필요하다.

다다스는 각 라면을 기다릴 때 최대 $K$만큼만 기다린다. 즉, $i$번 라면을 먹기 전 실제로 기다리는 시간은 $\min(A_i,K)$이다. 라면을 먹는 데 걸리는 시간은 $0$이며, 한 번에 하나의 라면만 준비한다.

따라서 모든 라면을 먹을 때까지 걸리는 총 시간은

이다.

총 시간이 정확히 $L$이 되도록 하는 양의 정수 $K$가 하나 이상 존재함이 보장된다. 조건을 만족하는 $K$의 최솟값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 테스트 케이스마다 조건을 만족하는 양의 정수 $K$의 최솟값을 한 줄에 하나씩 출력한다.

• $1 \le T \le 200\,000$.
• $1 \le N \le 200\,000$.
• $1\le A_{}$ ().