Valeur de Contraste

Énoncé du problème

Pour une séquence d'entiers $a_1, a_2, \dots, a_n$, nous définissons sa valeur de contraste comme : $|a_1-a_2|+|a_2-a_3|+\dots+|a_{n-1}-a_n|$.

Étant donné $T$ tests, pour chaque séquence $a$, nous devons trouver une sous-séquence $b$ telle que :

• $b$ n'est pas vide
• $b$ est une sous-séquence de $a$
• la valeur de contraste de $b$ est égale à celle de $a$

Le but est de déterminer la taille minimale possible pour $b$.

Description du problème

Pour un tableau d'entiesr $[a_1, a_2, \dots, a_n]$, nous appelons valeur de contraste la quantité $|a_1-a_2|+|a_2-a_3|+\cdots+|a_{n-1}-a_n|$. Notez que la valeur de contraste d'un tableau de taille 1 est 0.

Vous recevez un tableau d'entiers $a$. Votre tâche est de construire un tableau $b$ qui satisfait toutes les conditions suivantes :

• $b$ n'est pas vide, c'est-à-dire qu'il contient au moins un élément ;
• $b$ est une sous-séquence de $a$, c'est-à-dire que $b$ peut être obtenu en supprimant certains éléments de $a$ (éventuellement aucun) ;
• la valeur de contraste de $b$ est égale à celle de $a$.

Quelle est la taille minimale possible pour le tableau $b$ ?

Format d'entrée

La première ligne contient un entier unique $t$ ($1 \le t \le 10^4$) — le nombre de cas de test.

La première ligne de chaque cas de test contient un entier unique $n$ ($1 \le n \le 3 \cdot 10^5$) — la taille du tableau $a$.

La deuxième ligne contient $n$ entiers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — les éléments du tableau.

La somme de toutes les valeurs de $n$ sur les cas de test ne dépasse pas $3 \cdot 10^5$.

Format de sortie

Pour chaque cas de test, affichez un unique entier — la taille minimale possible du tableau $b$.

Exemple #1

Entrée d'exemple #1

4
5
1 3 3 3 7
2
4 2
4
1 1 1 1
7
5 4 2 1 0 0 4

Sortie d'exemple #1

2
2
1
3

// Valeur de Contraste
// Pour les tableaux strictement croissants ou décroissants, 
// la différence entre le premier et le dernier élément 
// est égale à la somme des différences entre éléments consécutifs
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int MAX = 1e6 + 10;
const int MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int test_cases;
    cin >> test_cases;
    
    while (test_cases--) {
        int taille;
        cin >> taille;
        
        vector<int> sequence;
        int precedent;
        cin >> precedent;
        sequence.push_back(precedent);
        
        // Suppression des doublons consécutifs
        for (int i = 1; i < taille; ++i) {
            int valeur_actuelle;
            cin >> valeur_actuelle;
            if (valeur_actuelle != precedent) {
                sequence.push_back(valeur_actuelle);
                precedent = valeur_actuelle;
            }
        }
        
        int taille_unique = sequence.size();
        int changements = 0;
        bool en_croissance = false;
        bool en_decroissance = true;
        
        // Compter les changements de tendance
        for (int i = 1; i < taille_unique; ++i) {
            if (sequence[i] > sequence[i-1] && en_decroissance) {
                changements++;
                en_croissance = true;
                en_decroissance = false;
            }
            if (sequence[i] < sequence[i-1] && en_croissance) {
                changements++;
                en_croissance = false;
                en_decroissance = true;
            }
        }
        
        cout << changements + 1 << "\n";
    }
    
    return 0;
}