문제1294--Best View

1294: Best View

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 104  통과: 28
[제출] [채점기록] [묻고답하기]

문제 설명

There are several skyscrapers arranged in a row. You're interested in finding the one from which the maximal number of other skyscrapers can be seen. The i-th skyscraper can be represented as a line segment on a plane with endpoints (i, 0) and (i, H[i]). A skyscraper can be seen from the roof of another skyscraper if a line segment connecting their roofs does not intersect with or touch any other skyscraper. Compute the maximal number of other skyscrapers that can be seen from the roof of some skyscraper.

입력 설명

The first line contains the number of test cases T (T ≤ 150).

For each test case, N (1 ≤ N ≤ 50) will be given on the first line.

The following line consists N integers separated by spaces, representing elements of H. Each element will be between 1 and 1,000,000,000, inclusive.

출력 설명

Output the answer of each test case on a separate line.

입력 예시 Copy

2
4
5 5 5 5
5
1 2 7 3 2

출력 예시 Copy

2
4

출처/분류