Đếm lần tăng/giảm giữa hai phần tử kề (Count Adjacent Increases and Decreases)

Nguồn: Phước Hưng OJ

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

Đề bài

Cho dãy $a_1,\ldots,a_n$. Gọi $U$ là số chỉ số $i\in[2,n]$ có $a_i>a_{i-1}$ và $D$ là số chỉ số có $a_i<a_{i-1}$. Trường hợp $a_i=a_{i-1}$ không thuộc nhóm nào. Hãy in $U$ và $D$.

Input

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

Output

In $U$ và $D$.

Subtask

Subtask 1 (20 điểm): $1\le n\le 50$; $|a_i|\le 100$.

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

Subtask 3 (50 điểm): $1\le n\le 100000$; $|a_i|\le 1000000000$.

Ví dụ

Input

6
3 5 5 2 7 1

Output

2 2

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.