P∞ — 神秘石板拼圖（Mystic Tablet Puzzle）

題目描述

在一座古老遺跡中，你發現了一塊刻滿符文的神秘石板。石板上排列著 N 個符文，每個符文皆為 1 到 9 之間的整數。考古學家推測，這些符文之間存在某種能量結合規律，若以正確順序進行合併，便能喚醒石板中的力量。

石板的符文按照順序排列，你可以反覆進行以下操作：

• 從石板上選擇任意一對相鄰符文 (a, b)，並將它們合併成一個新的符文。
• 合併規則為 f(a, b) = (a² + b²) mod 10
• 合併後，符文序列長度減一；原本的 a 與 b 消失，新的符文取代它們的位置。

你必須持續進行合併直到石板上只剩下一個符文為止。

由於不同的合併順序可能導致不同的最終符文，為了破解石板之謎，你需要找出所有可能結果之中最小的最終符文值。

輸入格式

第一行輸入一個整數 N，表示符文的數量。 第二行輸入 N 個整數 a1, a2, ..., aN，代表石板上的符文，由左至右依序排列。

限制條件

• 2 ≤ N ≤ 30
• 1 ≤ ai ≤ 9

輸出格式

輸出一個整數，即透過任意合法合併順序所能得到的最小最終符文值（0 至 9）。

樣例說明

若符文序列為：

3 4 2

可能的合併方式之一為：

1. 合併相鄰符文 (3, 4)，得到 (9 + 16) mod 10 = 5 石板變為：5 2
2. 合併 (5, 2)，得到 (25 + 4) mod 10 = 9

最終符文為 9。

然而，不同合併順序可能導致不同結果，你需要找出所有可能結果中的最小值。

輸入示例

3
3 4 2

輸出示例

9