Mountain Climbing

Time Limit : 1 sec, Memory Limit : 262144 KB

Problem B: Mountain Climbing

Problem

なりよし君は山登りの計画を立てています。計画はとても大切です。高原・盆地が多いのか、峰・窪地が多いのか、山腹があるのか、状況によって用意する荷物も変わってきます。

なりよし君が持っている登山ガイドブックには、今回登山に利用する道の一定の距離毎の標高がスタート地点からゴール地点まで順に書かれています。

ガイドブックに書かれている標高をスタート地点からゴール地点まで順に a1, a2, a3, ..., aNとし、高原、盆地、山腹、峰、窪地を次のように定義します:

  • 高原
    ai-1 < ai = ai+1 = ... = aj > aj+1 (1 < i < j < N)
  • 盆地
    ai-1 > ai = ai+1 = ... = aj < aj+1 (1 < i < j < N)
  • 山腹
    ai-1 < ai = ai+1 = ... = aj < aj+1 (1 < i < j < N)
    もしくは ai-1 > ai = ai+1 = ... = aj > aj+1 (1 < i < j < N)

  • ai-1 < ai > ai+1 (1 < i < N)
  • 窪地
    ai-1 > ai < ai+1 (1 < i < N)
高原
盆地
山腹
山腹
窪地

あなたは、なりよし君の為に、高原・盆地・山腹・峰・窪地、それぞれの数を計算するプログラムを書くことにしました。

Input

入力は次のような形式で与えられる:

N a1 a2 a3...aN

Nは与えられる標高の数を表す整数である。 aiは標高を表す整数である( 1 ≤ i ≤ N )。それぞれ空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

  • 1 ≤ N ≤ 100000
  • -100000 ≤ ai ≤ 100000

Output

高原の数、盆地の数、山腹、峰、窪地の数を順番に空白区切りで一行に出力せよ。

Sample Input 1

5 1 2 3 4 3

Sample Output 1

0 0 0 1 0

Sample Input 2

12 10 5 15 15 20 20 12 12 8 3 3 5

Sample Output 2

1 1 2 0 1