Breaking the Records (Breaking the Records)

Nguồn: HackerRank

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy điểm $a_1,\ldots,a_n$. Điểm $a_1$ thiết lập cả kỷ lục cao và thấp ban đầu. Với $i\ge2$, nếu $a_i$ lớn hơn mọi điểm trước đó thì kỷ lục cao bị phá; nếu $a_i$ nhỏ hơn mọi điểm trước đó thì kỷ lục thấp bị phá. Hãy đếm riêng số lần phá kỷ lục cao và thấp.

Input

Dòng 1 chứa $n$. Dòng 2 chứa $a_1,\ldots,a_n$.

Output

In hai số: số lần phá kỷ lục cao, rồi số lần phá kỷ lục thấp.

Subtask

Subtask 1 (20 điểm): $1\le n\le 20$; $0\le a_i\le 1000$.

Subtask 2 (30 điểm): $1\le n\le 200$; $0\le a_i\le 1000000$.

Subtask 3 (50 điểm): $1\le n\le 1000$; $0\le a_i\le 100000000$.

Ví dụ

Input

9
10 5 20 20 4 5 2 25 1

Output

2 4

Giải thích

Các giá trị được tính trực tiếp theo định nghĩa của đề; ví dụ này đồng thời minh họa đúng cận chỉ số của phép quét mảng.