Breaking the Records

Source: HackerRank

Version: Phuoc Hung OJ Extended

Problem

Given scores $a_1,\ldots,a_n$. The first score establishes both initial records. Count how many later scores are strictly greater than all previous scores and how many are strictly smaller than all previous scores.

Input

Line 1 contains $n$. Line 2 contains $a_1,\ldots,a_n$.

Output

Print the number of high-record breaks followed by the number of low-record breaks.

Subtasks

Subtask 1 (20 points): $1\le n\le 20$; $0\le a_i\le 1000$.

Subtask 2 (30 points): $1\le n\le 200$; $0\le a_i\le 1000000$.

Subtask 3 (50 points): $1\le n\le 1000$; $0\le a_i\le 100000000$.

Example

Input

9
10 5 20 20 4 5 2 25 1

Output

2 4

Explanation

The values follow directly from the definitions and illustrate the valid index range of the array scan.