P2P

Escrito por Enzo Dantas

"Peer-to-peer ou P2P é uma arquitetura de redes de computadores onde cada um dos vértices da rede funciona tanto como cliente quanto como servidor, permitindo compartilhamentos de dados sem a necessidade de um servidor central, mudando um paradigma existente."

- Wikipédia

A arquitetura P2P é usada na maioria das criptomoedas, no Skype, e foi usada pelo Spotify durante os primeiros 8 anos da empresa*.

De grosso modo, imagine que eu quero acessar uma informação (um vídeo, por exemplo): em vez de pegar essa informação de um servidor que contém essa informação baixada, o sistema vai realizar uma busca entre outros usuários até achar alguém que tenha essa informação baixada.

Odina, cientista da computação que trabalha no setor de P&D do Spotify, faz parte de um projeto que busca explorar otimizações e aplicações do P2P para possivelmente trazê-lo de volta. Odina, que foi encarregado de otimizar o algoritmo de busca do P2P, apresentou o seguinte algoritmo: quando um usuário quer acessar uma música, um sistema central vai realizar chamadas para um grupo de usuários tal que alguém entre esses usuários possui a música baixada. Todo usuário tem uma posição $p_i$ e todas as posições são distintas. A distância entre dois usuários $i$ e $j$ é $|p_i - p_j|$. Todo usuário $i$ que receber uma chamada vai chamar o usuário $j$ mais próximo dele (caso haja empate, o usuário de menor $p_j$ é chamado). Acontece que o processo de o sistema central realizar uma chamada é relativamente lento, então Odina quer minimizar o número dessas chamadas. Dado a quantidade de usuários do grupo e a posição de cada um, determine qual é o número mínimo de chamadas que devem ser feitas pelo sistema central para garantir que todos os usuários desse grupo serão chamados (pelo sistema central ou por outro usuário) e a música será achada.

Input:
A primeira linha contém um inteiro $N$ $(1 \le N \le 100)$ - a quantidade de usuários do grupo.

A próxima linha contém $N$ inteiros $p_1, p_2, \dots , p_n$ dizendo a posição de cada usuário.

Output:
Seu programa deve imprimir um único número: a resposta do problema.

Exemplo:

5
7 1 3 11 4

2

Se o sistema central chamar os vértices nas posições 1 e 11, todos os usuários serão chamados.

Para submeter a sua solução, use esse link

*Nota do autor:

A série "The Playlist" da Netflix conta a história do surgimento do Spotify de vários pontos de vista (fundador, indústria, artista, etc.) e mostra o impacto da empresa em diversos segmentos da sociedade (recomendo!). O episódio 4, em particular, conta a história da visão do programador e mostra ideias e aplicações muito interessantes de informática/ciência da computação.