I_love_%username% (I_love_%username%)

Nguồn: Codeforces

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

Đề bài

Cho dãy điểm $a_1,\ldots,a_n$ theo thứ tự thời gian. Với $i\ge2$, lần thứ $i$ được gọi là đáng kinh ngạc nếu $a_i>\max(a_1,\ldots,a_{i-1})$ hoặc $a_i<\min(a_1,\ldots,a_{i-1})$. Lần đầu không được tính. Hãy đếm số lần đáng kinh ngạc.

Input

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

Output

In đáp án là một số nguyên.

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 5000$.

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

Ví dụ

Input

5
100 50 200 150 200

Output

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.