我叫做基德，是一名刑警

0 Judge

Code: 0

基德是一名充滿熱血與幹勁的年輕人，他住在一座美麗的沿海小鎮，職業是一名警員。

基德管轄的街區是小鎮最黑暗的無法地帶，此區由$N$個街口組成，每個街口都被一個邪惡組織佔據，第$i$個街口的邪惡組織的邪惡度為$a_i$，這些組織經常聯合舉辦一些邪教活動，嘗試召喚各種惡魔，非常危險。
根據多年的執勤經驗，基德發現邪惡組織的活動有以下規律:

在翻閱無數資料後，基德最後歸納出了一個法則，那就是:

若一段連續的街口$l, l + 1, l + 2, ..., r$聯合舉辦邪教活動，則$\max \{\left| a[i] - a[j] \right| : l \leq i, j \leq r \} \leq r - l + 1$。

這個式子代表的意義是，一個邪教活動能夠辦成，則「任兩個參與組織的邪惡度相差絕對值」不會超過「參與活動的組織數」。

例如: 有5個組織，邪惡度分別為[11, 7, 10, 9, 11]，則邪惡度[7, 10]的組織不會共同舉辦活動，但[11, 7, 10, 9]有可能共同舉辦活動。
請注意每次活動必定是由連續一段街口的組織共同舉辦。

給定盤據$N$個街口的組織分別的邪惡度，基德想請你幫忙計算出每個組織$i$可能參與的最大活動規模，以及有多少種不同的組合會達到此規模，一個活動的規模即參與的組織數量。

輸入

在本題目中，一個檔案只會有一筆測資。
第一行有一個整數$N$。
第二行有$N$個整數，第$i$個整數代表$a_i$。

輸出$N$行，每一行有兩個整數，分別為街口$i$的組織可能參與的最大活動規模，及多少種不同的活動可在包含組織$i$的前提下達到此規模。

大測資(100%):
$1 \leq N \leq 10^6$
$0 \leq a_i < 10^7$

中測資(50%):
額外限制 $N \leq 10^3$

小測資(20%):
額外限制 $N \leq 15$

5
11 7 10 9 11

此例子下所有組織有可能共同舉辦活動，每個組織參與的最大規模活動都是[11, 7, 10, 9, 11]，參與組織數量為5，只有1種可能。

11
14 13 11 10 8 7 5 4 3 1 0

邪惡度10的組織可能參與的最大規模為[14, 13, 11, 10]及[11, 10, 8, 7]兩種

6
1 1 1 100 1 1

請注意只有連續的街口會共同舉辦活動，左邊邪惡度為1的組織們不能跳過中間邪惡度為100的組織，跟右邊邪惡度為1的組織舉辦活動。

run-time limit: 7000 ms
memory limit: 536870912 byte
測資數量: 7