Mảng con tuần hoàn vượt trội

Cho một mảng tuần hoàn vô hạn $a_0,a_1,a_2,\dots$ với chu kỳ độ dài $n$. Cụ thể, $a_i=a_{imodn}$ với mọi $i\ge 0$.

Một mảng con tuần hoàn $(l,s)$ với $0\le l<n$ và $1\le s<n$ là một mảng tuần hoàn vô hạn có chu kỳ độ dài $s$, được hình thành bằng cách ghép vô hạn lần đoạn $a_l,a_{l+1},\dots ,a_{l+s-1}$ (chỉ số lấy theo $modn$). Khi đặt mảng con này chồng lên $a$ bắt đầu từ vị trí $l$, phần tử thứ $k$ ($k\ge 0$) của nó tương ứng với $a_{(l+k)modn}$ của mảng $a$, còn chính nó nhận giá trị $a_{(l+(kmods))modn}$.

Mảng con $(l,s)$ được gọi là vượt trội (superior) nếu mọi phần tử của nó đều lớn hơn hoặc bằng phần tử tương ứng của mảng $a$, tức là với mọi $k\ge 0$ ta có

$$a_{(l+(kmods))modn}\ge a_{(l+k)modn}.$$

Hãy đếm số cặp $(l,s)$ ứng với các mảng con tuần hoàn vượt trội.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_0,a_1,\dots ,a_{n-1}$ cách nhau bởi dấu cách.

Dữ liệu ra

• Một số nguyên duy nhất — số cặp $(l,s)$ ứng với mảng con tuần hoàn vượt trội.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le a_i\le {10}^6$

Ví dụ