The Medali Gym is found in West Province (Area Three) and features the Normal Type Gym Leader, Larry.

How to Reach the Medali Gym
You can reach Medali if you go east from Porto Marinada, where you will go during the Cascarrafa Gym Test.
Gym Test
Talk to the person behind the counter in the Medali Gym, who will tell you about the Gym Test. There are three trainers that you can battle in Medali, and each one has been given a clue. They have to tell you their clue if you defeat them. You will also get a clue: "find out how the regulars season their dishes."
Go outside and go southeast to the destination on the map to find the Treasure Eatery. Go inside, but don't talk to the waiter yet. Instead, go past the waiter and talk to the person at the end of the bar. They will mention lemon.
Then go outside and go west, where you can talk to a trainer to battle Adara the Student, who has a level 34 Gumshoos and a level 34 Greedent. You get 4760 Pokédollars for winning.
Afterward, talk to the trainer to get the clue "look for something that's the odd one out at one of the ice cream stands."
Go northwest to the nearby ice cream cart and talk to the person to see the menu. Go to the bottom of the menu and you will see Grilled Rice Balls with lemon.
In the northwestern part of town, near the southwest side of the gym building, talk to the trainer to battle Gisela the Student, who has a level 34 Ursaring. You get 4760 Pokédollars for winning.
Talk to the trainer after the battle to get the clue "look for a dark spot surrounded by stairs".
Go down the nearby stairs and check on the bars, where you see a message that says "Fire Blast".
In the southwest corner of town, talk to the trainer to battle Santiago the Student, who has a level 34 Dunsparce. You get 4760 Pokédollars for winning.
Afterward, talk to the trainer to get another clue: "listen really closely to the blue bird Pokémon".
Go northeast to find someone with a blue bird on their head. Go near them and watch what they say, and you will see the clue "Meedyum" (i.e. Medium).
Now you have all four clues, so go back into the Treasure Eatery (where the map destination is) and talk to the waiter near the door. Order the following:
When you're ready to battle the gym leader, talk to the waiter again and say Yes.
Normal Gym Leader Larry, the Exceptional Everyman
Larry has a level 35 Komala, a level 35 Dudunsparce, and a level 36 Staraptor that he Terastallizes, with Tera Type Normal. You get 6480 Pokédollars for winning.
You will get a Gym Badge. Check the Gym Badge Effects page to see the level of Pokémon that will listen to you and be easier to catch, or open the Map App or Pokédex App and press X, then select Profile, then press A to see the effects of your current badges.
You also get a TM025 Facade.
This was your fifth Gym Badge, Geeta will heal up your Pokémon, and you will battle Nemona, who has a level 36 Lycanroc, a level 36 Goomy, a level 36 Pawmo, and a level 37 starter (Quaquaval if you chose Sprigatito, Meowscarada if you chose Fuecoco, Skeledirge if you chose Quaxly). She will Terastallize this Pokémon, with the same Tera Type as its usual type. You get 4440 Pokédollars for winning.
Afterward, Geeta will give you some TM171s Tera Blast. This move will match the Tera Type of your Pokémon if you have Terastallized it.
Change Pokémon Tera Type
You can now go to the Treasure Eatery and talk to the person behind the bar to receive 50 Normal Tera Shards. Whenever you talk to this person, if you have 50 Tera Shards of a specific type, you can select a Pokémon to change its Tera Type to the selected type.
New Sandwiches
A new Gym Badge means new sandwich recipes. Be sure to stop by any Every Wich Way and talk to the person in front of the counter to learn some new recipes.