Biến đổi mã gen

Giáo sư 3M vừa mới phát hiện ra sinh vật mới chưa từng xuất hiện trước đây. Sinh vật này rất
kì lạ khi có thể thay đổi mã gen của mình. Mã gen của sinh vật được biển diễn dưới dạng một
dãy các phần tử số nguyên. Được biết trong vòng đời của sinh vật có thể biến đổi duy nhất \(1\)
lần trong đoạn gen từ \(L\) đến \(R\) bằng cách thay đổi các số nguyên trong trên dãy thành \(a_L\).
Giáo sư muốn biết với mã gen đã cho sinh vật này có thể biến đổi thành bao nhiêu mã gen
khác nhau. Các bạn hãy giúp giáo sư 3M nhé.

Input

Vào từ file văn bản GCC.INP:

• Dòng đầu ghi số nguyên dương \(n\) \((1 \leq n \leq 10^6)\)
• Dòng thứ \(2\) ghi \(n\) số nguyên \(a_i\) \((1 \leq |a_i| \leq 10^6)\).

Output

Ghi ra file văn bản GCC.OUT:

• Gồm một số nguyên dương duy nhất là số mã gen khác nhau có thể.

Example

4 1
1 2 3

4

Scoring

• \(10\%\) số test tương ứng với \(10\%\) số điểm của \(n \leq 500\).
• \(20\%\) số test tương ứng với \(20\%\) số điểm của \(n \leq 10^3\), \(1 \leq a_i \leq 9\).
• \(20\%\) số test tương ứng với \(20\%\) số điểm có các phần tử \(a_i\) phân biệt.
• \(20\%\) số test tương ứng với \(20\%\) số điểm của \(n \leq 10000\).
• \(30\%\) số test còn lại tương ứng với \(30\%\) số điểm của bài không có ràng buộc gì thêm