English · Original
Chinese · Translation
Formal · Original
Valery is very interested in magic. Magic attracts him so much that he sees it everywhere. He explains any strange and weird phenomenon through intervention of supernatural forces. But who would have thought that even in a regular array of numbers Valera manages to see something beautiful and magical.
Valera absolutely accidentally got a piece of ancient parchment on which an array of numbers was written. He immediately thought that the numbers in this array were not random. As a result of extensive research Valera worked out a wonderful property that a magical array should have: an array is defined as magic if its **minimum and maximum coincide**.
He decided to share this outstanding discovery with you, but he asks you for help in return. Despite the tremendous intelligence and wit, Valera counts very badly and so you will have to complete his work. All you have to do is count the number of magical subarrays of the original array of numbers, written on the parchment. Subarray is defined as **non-empty sequence of consecutive elements**.
## Input
The first line of the input data contains an integer _n_ (1 ≤ _n_ ≤ 105). The second line contains an array of original integers _a_1, _a_2, ..., _a__n_ ( - 109 ≤ _a__i_ ≤ 109).
## Output
Print on the single line the answer to the problem: the amount of subarrays, which are magical.
Please do not use the _%lld_ specificator to read or write 64-bit numbers in C++. It is recommended to use _cin_, _cout_ streams (you can also use the _%I64d_ specificator).
[samples]
## Note
Notes to sample tests:
Magical subarrays are shown with pairs of indices \[a;b\] of the beginning and the end.
In the first sample: \[1;1\], \[2;2\], \[3;3\], \[4;4\], \[2;3\].
In the second sample: \[1;1\], \[2;2\], \[3;3\], \[4;4\], \[5;5\], \[1;2\], \[2;3\], \[1;3\].
[{"iden":"statement","content":"#cf_span(class=[tex-font-style-underline], body=[瓦列里对魔法非常感兴趣。魔法对他有着极大的吸引力，以至于他无处不在地看到魔法。他用超自然力量的存在来解释任何奇怪和诡异的现象。但谁会想到，即使在普通的数字数组中，瓦列里也能看到美丽而神奇的东西。])\n\n瓦列里偶然得到了一张古老的羊皮纸，上面写有一个数字数组。他立刻认为这个数组中的数字并非随机。经过广泛研究，瓦列里发现了一个神奇数组应有的美妙性质：如果一个数组的*最小值和最大值相等*，则称其为魔法数组。\n\n他决定与你分享这一杰出发现，但为此他需要你的帮助。尽管瓦列里聪慧过人，但他计算能力很差，因此你必须完成他的工作。你所需要做的就是计算原始数组中魔法子数组的数量。子数组定义为*非空的连续元素序列*。\n\n输入数据的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105])。第二行包含原始整数数组 #cf_span[a1, a2, ..., an] (#cf_span[ - 109 ≤ ai ≤ 109])。\n\n请在单行上输出问题的答案：魔法子数组的数量。\n\n请不要在 C++ 中使用 _%lld_ 标识符来读取或写入 64 位数字。建议使用 _cin_、_cout_ 流（你也可以使用 _%I64d_ 标识符）。\n\n样例说明：\n\n魔法子数组用起始和结束位置的索引对 [a;b] 表示。\n\n在第一个样例中：[1;1], [2;2], [3;3], [4;4], [2;3]。\n\n在第二个样例中：[1;1], [2;2], [3;3], [4;4], [5;5], [1;2], [2;3], [1;3]。 \n\n"},{"iden":"input","content":"输入数据的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105])。第二行包含原始整数数组 #cf_span[a1, a2, ..., an] (#cf_span[ - 109 ≤ ai ≤ 109])。 "},{"iden":"output","content":"请在单行上输出问题的答案：魔法子数组的数量。请不要在 C++ 中使用 _%lld_ 标识符来读取或写入 64 位数字。建议使用 _cin_、_cout_ 流（你也可以使用 _%I64d_ 标识符）。"},{"iden":"examples","content":"输入42 1 1 4输出5输入5-2 -2 -2 0 1输出8"},{"iden":"note","content":"样例说明：魔法子数组用起始和结束位置的索引对 [a;b] 表示。在第一个样例中：[1;1], [2;2], [3;3], [4;4], [2;3]。在第二个样例中：[1;1], [2;2], [3;3], [4;4], [5;5], [1;2], [2;3], [1;3]。 "}]}
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the length of the array.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers, where $ a_i \in \mathbb{Z} $ for all $ i \in \{1, \dots, n\} $.
A *subarray* is a contiguous subsequence $ A[i:j] = (a_i, a_{i+1}, \dots, a_j) $ for $ 1 \leq i \leq j \leq n $.
A subarray $ A[i:j] $ is *magical* if its minimum and maximum elements are equal, i.e.,
$$
\min_{k=i}^j a_k = \max_{k=i}^j a_k
$$
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ -10^9 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Count the number of magical subarrays in $ A $, i.e., compute:
$$
\left| \left\{ (i,j) \in \mathbb{Z}^2 \mid 1 \leq i \leq j \leq n \text{ and } \min_{k=i}^j a_k = \max_{k=i}^j a_k \right\} \right|
$$
API Response (JSON)
{
"problem": {
"name": "B. Magical Array",
"description": {
"content": "Valery is very interested in magic. Magic attracts him so much that he sees it everywhere. He explains any strange and weird phenomenon through intervention of supernatural forces. But who would have ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF84B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Valery is very interested in magic. Magic attracts him so much that he sees it everywhere. He explains any strange and weird phenomenon through intervention of supernatural forces. But who would have ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"#cf_span(class=[tex-font-style-underline], body=[瓦列里对魔法非常感兴趣。魔法对他有着极大的吸引力，以至于他无处不在地看到魔法。他用超自然力量的存在来解释任何奇怪和诡异的现象。但谁会想到，即使在普通的数字数组中，瓦列里也能看到美丽而神奇的东西。])\\n\\n瓦列里偶然得到了一张古老的羊皮纸...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the array. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers, where $ a_i \\in \\mathbb{Z} $ for all $ i \\in \\{1, \\dots, n\\} $....",
"is_translate": false,
"language": "Formal"
}
]
}