Thành phố XYZ đã trở nên hiện đại nhờ sự tiến bộ đột phá trong phát triển kinh tế. Trong lần cải cách lần này, thành phố muốn tập trung vào việc phát triển đô thị và nâng cao chất lượng giao thông của thành phố. Để làm được điều này, Chủ tịch thành phố muốn khảo sát và đánh giá các tuyến đường của thành phố. Chủ tịch đặc biệt chú ý đến cao tốc nối XYZ với HCM, con đường huyết mạch của XYZ với ~N~ địa điểm đặc biệt khác. Các địa điểm nối tiếp với nhau theo chỉ số, địa điểm ~i~ sẽ có giá trị ~a_i~. Điểm chung của 2 địa điểm là ước chung lớn nhất của 2 giá trị thuộc hai địa điểm đó. Để phát triển đô thị, Chủ tịch thành phố cần khảo sát với một đoạn trên tuyến đường như sau: Một đoạn đường được coi là hoàn hảo nếu như địa điểm có giá trị lớn nhất và địa điểm có giá trị nhỏ nhất có điểm chung là 1. Là một người nhìn xa trông rộng, Chủ tịch thành phố XYZ muốn biết có bao nhiêu đoạn đường hoàn hảo như thế trên cao tốc nối XYZ- HCM. Bạn hãy giúp Chủ tịch tìm ra đáp án chính xác.

Yêu cầu: Hãy cho biết số lượng đoạn đường hoàn hảo trên tuyến đường cao tốc XYZ- HCM.

Input

• Dòng đầu tiên gồm một số nguyên dương ~N~ (~1 \le N \le 10^5~) là số lượng địa điểm trên tuyến đường.
• Dòng thứ hai chứa dãy số nguyên dương ~a_1, a_2, \dots, a_N~ với ~1 \le a_i \le 10^5~, ~1 \le i \le N~ là giá trị của địa điểm thứ ~i~.

Output

• Một dòng duy nhất là đáp án bài toán.

Sample Input 1

5
5 3 1 2 4

Sample Output 1

10