Dạ hội cuối năm (prom) là một sự kiện trọng đại trước khi kết thúc năm học ở trường THPT chuyên Lê Quý Đôn. Vì đã là năm cuối cấp nên Minh Huy quyết tâm mời cho bằng được chị Constant tham gia khiêu vũ cùng mình. Tiếc thay, chị Constant đã nhận lời mời làm bạn nhảy của chuyên gia tin học Flow God (dưới tư cách cựu học sinh) nên đành phải từ chối Minh Huy. Không bỏ cuộc, Minh Huy liên tục đưa ra những hứa hẹn đầy hấp dẫn để lôi kéo khiến chị Constant phải đôi chút xiêu lòng: Chị Constant đồng ý hủy hẹn với Flow God để đi với Minh Huy nếu như cậu có thể tính được số lượng dãy con có độ cồng kềnh nhỏ nhất trong một dãy số.

Với một dãy số nguyên dương gồm \(n\) số \(a_1,a_2,\cdots,a_n\), độ cồng kềnh của một dãy con liên tiếp \(a_i,a_{i+1},\cdots,a_j\) là hiệu của số lớn nhất trong dãy và số nhỏ nhất trong dãy. Ví dụ: độ cồng kềnh của \([1,3,2]\) là \(3−1=2\).

Chị Constant muốn tìm dãy con liên tiếp có độ cồng kềnh nhỏ nhất có thể, và tổng quát hơn, đếm xem có bao nhiêu dãy con liên tiếp có độ cồng kềnh nhỏ nhất như thế. Bạn hãy giúp Minh Huy giải đáp lời thách đố này để được dự prom cùng chị Constant nhé!

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\)
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,\cdots,a_n (1 \leq a_i \leq n)\)

Output

• In ra một số nguyên dương, là số lượng dãy con liên tiếp có độ cồng kềnh nhỏ nhất.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 300\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 3,000\).
• Subtask \(3\) (\(40\%\) số điểm): \(n \leq 300,000\).

Example

3
1 1 1 

6