트로피 진열

면접 대비

시간 제한2초메모리 제한128 MB

요약

트로피 높이 배열을 왼쪽과 오른쪽에서 각각 훑어 이전 트로피보다 더 큰 값이 나올 때마다 세어 보이는 개수를 구합니다.

난이도: 쉬움10점 중 2점
유형: 배열, 구현
정답자: 아직 제출이 없습니다

문제

민식이는 여러 로봇 대회에서 우승해 집에 많은 트로피를 가지고 있다. 그는 트로피들을 일렬로 놓인 선반 위에 왼쪽부터 오른쪽 순서대로 올려두었다. 방문을 열고 들어가면 처음에는 선반의 왼쪽에서 트로피들을 보게 된다. 이때 앞쪽에 있는 더 높은 트로피는 뒤쪽의 낮은 트로피를 가린다.

어떤 방향에서 볼 때, 한 트로피는 그 방향에서 자신보다 앞에 있는 모든 트로피보다 높을 때만 보인다. 민식이는 선반을 180도 돌려 오른쪽에서도 같은 방식으로 트로피들을 볼 수 있다.

트로피 높이가 왼쪽부터 주어질 때, 왼쪽에서 보이는 트로피 수와 오른쪽에서 보이는 트로피 수를 구하라.

입력

첫째 줄에 트로피의 개수 N (1 ≤ N ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 왼쪽에 있는 트로피부터 차례대로 높이가 하나씩 주어진다. 각 트로피의 높이는 100 이하의 자연수이다.

출력

첫째 줄에 왼쪽에서 보이는 트로피의 개수를 출력한다. 둘째 줄에 오른쪽에서 보이는 트로피의 개수를 출력한다.

예제4

예제 1
입력
```
5
1
2
3
4
5
```
예상 출력
```
5
1
```
예제 2
입력
```
4
5
5
5
5
```
예상 출력
```
1
1
```
예제 3
입력
```
5
1
2
5
2
1
```
예상 출력
```
3
3
```
예제 4
입력
```
7
1
4
2
5
3
7
1
```
예상 출력
```
4
2
```