높이가 서로 다를 수도 같은 수도 있는 막대기 \(n\)개가 한 줄로 서 있다.

왼쪽에서 바라볼 때 보이는 막대기의 개수와 오른쪽에서 바라볼 때 보이는 막대기의 개수를 각각 구하라.

어떤 막대기보다 바라보는 방향 앞쪽에 더 높거나 같은 높이의 막대기가 있으면 그 막대기는 보이지 않는다.

입력

첫째 줄에 막대기의 개수 \(n\)이 주어진다.

둘째 줄에 막대기 높이 \(n\)개가 공백으로 구분되어 주어진다.

\((1 \le n \le 100000)\)

각 막대기의 높이는 \(1\) 이상 \(100000\) 이하이다.

출력

첫째 줄에 왼쪽에서 보이는 막대기의 개수를 출력한다.

둘째 줄에 오른쪽에서 보이는 막대기의 개수를 출력한다.

예제 입력

5
1 3 2 5 4

예제 출력

3
2