69. 我叫做基德,是一名刑警

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$

範例輸入1

5
11 7 10 9 11

範例輸出1

5 1
5 1
5 1
5 1
5 1

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

範例輸入2

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

範例輸出2

4 1
4 1
4 2
4 2
5 1
5 1
5 2
5 2
5 2
5 1
5 1

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

範例輸入3

6
1 1 1 100 1 1

範例輸出3

3 1
3 1
3 1
1 1
2 1
2 1

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


Judge Setting

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