#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vl vector<long long>
#define pl pair<long long, long long>
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n, q;
if (!(cin >> n >> q)) return 0;
// 1. Načtení a spočítání četností
vl input_nums(n);
map<ll, ll> counts;
for (ll i = 0; i < n; i++){
cin >> input_nums[i];
counts[input_nums[i]]++;
}
ll l_query, r_query;
cin >> l_query >> r_query; // Jen načteme, v Q=1 se nepoužívá specificky jinak než přes celé pole
// 2. Vytvoření párů {četnost, druh}
vector<pl> pary;
for (auto const& [species, count] : counts) {
pary.push_back({count, species});
}
// 3. Seřazení od nejméně častých po nejčastější
sort(pary.begin(), pary.end());
// 4. Konstrukce optimálního rozložení (Mountain shape)
// Použijeme deque pro vkládání z krajů
deque<ll> final_blocks;
// Procházíme seřazené páry a střídavě dáváme doleva a doprava
for (int i = 0; i < pary.size(); i++) {
ll count = pary[i].first;
ll species = pary[i].second;
// Pokud je 'i' sudé, dáme na začátek (vlevo), liché na konec (vpravo)
// Tím dostaneme nejmenší na úplné kraje a největší doprostřed.
if (i % 2 == 0) {
// Přidáme blok zleva
for(int k=0; k<count; k++) final_blocks.push_front(species);
} else {
// Přidáme blok zprava
for(int k=0; k<count; k++) final_blocks.push_back(species);
}
}
// Převedeme deque zpět na vector pro DP výpočet
vl nums(final_blocks.begin(), final_blocks.end());
// 5. DP výpočet (tento byl správně, jen na špatně seřazeném poli)
vl dp(n, 1);
// Base case: dp[0] = 1 (jeden prvek má diverzitu 1)
for (ll i = 1; i < n; i++){
if (nums[i] == nums[i-1]){
// Stejný druh jako předchozí -> nepřidává novou diverzitu do existujících suffixů
dp[i] = dp[i-1] + 1;
}
else{
// Jiný druh -> pro všechny suffixy končící na i-1 se diverzita zvýší o 1
// + vznikne 1 nový suffix (samotný prvek i)
// Celkem se přičte: (i) + 1 = i + 1
dp[i] = dp[i-1] + (i + 1);
}
}
ll suma = 0;
for (ll i = 0; i < n; i++){
suma += dp[i];
}
cout << suma << "\n";
return 0;
}
