Count Adjacent Increases and Decreases

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem

Given $a_1,\ldots,a_n$, let $U$ count adjacent strict increases and $D$ count adjacent strict decreases. Equal adjacent values count toward neither. Print $U$ and $D$.

Input

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

Output

Print $U$ and $D$.

Subtasks

Subtask 1 (20 points): $1\le n\le 50$; $|a_i|\le 100$.

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

Subtask 3 (50 points): $1\le n\le 100000$; $|a_i|\le 1000000000$.

Example

Input

6
3 5 5 2 7 1

Output

2 2

Explanation

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