## Algorithm

Problem Name: 2 AD-HOC - beecrowd | 1089

# Musical Loop

By Ricardo Anido  Brazil

Timelimit: 1

A musical loop is a small section of music composed to be played continuously (that is, the section is played again when it reaches the end), in a seamless way. Loops are used in many styles of popular music (hip hop, techno, etc), as well in computer games, especially casual games on the Internet.

Loops may be digitalized for example using PCM (Pulse Code Modulation), a technique for representing analog signals used extensively in digital audio. In PCM, the magnitude of the signal is sampled at regular intervals, and the values sampled are stored in sequence. To produce the sound for the sampled data, the procedure is applied in reverse (demodulation).

Fernanda works for a game software house, and composed a beautiful musical loop, coded in PCM. Analyzing the waveform of her loop in audio editing software, Fernanda became curious when she noticed the number of "peaks". A peak in a waveform is the value of a sample that represents a local maximum or minimum. The figure below illustrates (a) a waveform and (b) the loop formed with this waveform, containing 48 peaks.

Fernandinha is a dear friend of yours. She has asked your help to determine how many peaks exist in her musical loop.

## Input

The input contains several test cases. The first line of a test case contains one integer N, representing the number of samples in the musical loop composed by Fernanda (2 ≤ N ≤ 104). The second line contains N integers Hi, separated by spaces, representing the sequence of magnitudes sampled (-104 ≤ Hi ≤ 104 for 1 ≤ i ≤ N, H1 ≠ HN and Hi ≠ Hi+1 for 1 ≤ i < N). Notice that H1 follows HN when the loop is played.

The end of the input is indicated by a line that contains only one zero.

## Output

For each test case in the input your program must print a single line, containing one integer, the number of peaks that exist in the musical loop.

 Input Sample Output Sample 2 1 -3 6 40 0 -41 0 41 42 4 300 450 449 450 0 2 2 4

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0

int main(int argc, char **argv)
{

int n, i, ans;
int ondas[10050];

while (scanf("%d", &n), n)
{

for (i = 0; i  <  n; ++i)
scanf("%d", &ondas[i]);

ans = 0;
for (i = 1; i  <  n - 1; ++i)
if ((ondas[i] - ondas[i - 1]) * (ondas[i] - ondas[i + 1]) > 0)
++ans;

if ((ondas[0] - ondas[n - 1]) * (ondas[0] - ondas[1]) > 0)
++ans;
if ((ondas[n - 1] - ondas[n - 2]) * (ondas[n - 1] - ondas[0]) > 0)
++ans;

printf("%d\n", ans);

}

return 0;

}
``````
Copy The Code &

Input

cmd
2
1 -3
6
40 0 -41 0 41 42
4
300 450 449 450
0

Output

cmd
2
2
4

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <iostream>
#include <vector>

using namespace std;

int main()
{
int n, x, c;

while (1)
{
cin >> n;
if (n==0)
break;
c=0;
vector<int>v;
vector < char>s;

while (n--)
{
cin >> x;
v.push_back(x);
}
v.push_back(v[0]);
v.push_back(v[1]);

for (int i = 0; i  <  v.size()-1; ++i)
{
if (v[i] <= v[i+1])
s.push_back('u');
else
s.push_back('d');
}
for (int i = 0; i  <  s.size()-1; ++i)
{
if (s[i]!=s[i+1])
c++;
}
cout << c << endl;
}

return 0;
}
``````
Copy The Code &

Input

cmd
2
1 -3
6
40 0 -41 0 41 42
4
300 450 449 450
0

Output

cmd
2
2
4

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const { readFileSync } = require("fs")
const input = readFileSync("/dev/stdin", "utf8").split("\n").map((line) => line.split(" "))

/**
* @param {string | any[]} arr
* @param {number} pos
*/
const at = (arr, pos) => arr[(arr.length + pos) % arr.length]

/** @param {number[]} nums  */
function countInflections(nums) {
if (nums.length <= 1) return nums.length

let count = 0
let prevInflectionPoint = at(nums, -1)

nums.forEach((curr, index, arr) => {
const next = at(arr, index + 1)
// Ambos estão descendo ou subindo:
// 9 -> DESCEU -> 6 -> DESCEU -> 5
// PREV ->     CURR ->         NEXT

// INFLECÇÃO:
// 9 -> DESCEU -> 5 -> SUBIU  -> 10
// PREV ->     CURR ->         NEXT
// prevInflectionPoint = curr

// CURR === NEXT  <=>  Não faz nada
// 5 -> DESCEU -> 10 -> IGUA  -> 10
// PREV ->     CURR ->         NEXT
if (curr !== next) {
if (Math.sign(curr - prevInflectionPoint) != Math.sign(next - curr)) {
count += 1
prevInflectionPoint = curr
}
}
})

return count
}

function main() {
const responses = []

for (let index = 0; index  <  input.length; index += 2) {
const [N] = input[index]
if (N == "0") break

const nums = input[index + 1].slice(0, +N).map((n) => Number.parseInt(n, 10))
responses.push(countInflections(nums))
}

console.log(responses.join("\n"))
}

main()
``````
Copy The Code &

Input

cmd
2
1 -3
6
40 0 -41 0 41 42
4
300 450 449 450
0

Output

cmd
2
2
4

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const { readFileSync } = require("fs")

.split("\n")
.map(line => line
.split(" ")
.map(value => Number.parseInt(value, 10))
)

/** @param {number[]} nums  */

function countInflections(nums) {
if (nums.length <= 1) return nums.length

let count = 0
let prevInflectionPoint = nums.at(-1)

nums.forEach((curr, index, arr) => {
const next = arr.at(index + 1)

if (curr !== next) {
if (Math.sign(curr - prevInflectionPoint) != Math.sign(next - curr)) {
count += 1
prevInflectionPoint = curr
}
}
})

return count
}

function main() {
const responses = []

for (let index = 0; index  <  input.length; index += 2) {
const [N] = input[index]

if (N === 0)
break

responses.push(
countInflections(input[index + 1].slice(0, N))
)
}

console.log(responses.join("\n"))
}

main()
``````
Copy The Code &

Input

cmd
2
1 -3
6
40 0 -41 0 41 42
4
300 450 449 450
0

Output

cmd
2
2
4

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
while True:
n = int(input())
if n == 0: break
v = [int(x) for x in input().split()]
a = True if v[-1] < v[0] else False
p = 0
for i in range(1, n):
if v[i-1] < v[i]: s = True
else: s = False
if s != a: p += 1
a = s
if v[-1] < v[0]: s = True
else: s = False
if s != a: p += 1
print(p)
``````
Copy The Code &

Input

cmd
2
1 -3
6
40 0 -41 0 41 42
4
300 450 449 450
0

Output

cmd
2
2
4