+ مدة الزمن المحددة: 1ثانية
+ حد الذاكرة: 256 ميجابايت
----------
توجد مجموعة من الطائرات الحربية مصفوفة في صف وارتفاع كل واحدة منها مختلف عن الأخرى. كل طائرة حربية يمكنها استهداف الطائرات الحربية التي تقع أمامها فقط، وذلك بشرط أن يكون ارتفاع الطائرة المستهدفة أقل من ارتفاعها.
العدد الذي يمكن لطائرة حربية معينة استهدافه من الطائرات الحربية الأمامية يسمى **العدد الاستراتيجي**. على سبيل المثال، إذا كان بإمكان الطائرة الحربية ألف استهداف 3 طائرات حربية، فإننا نقول أن العدد الاستراتيجي للطائرة الحربية ألف هو 3.
يجب عليك حساب مجموع الأعداد الاستراتيجية لجميع الطائرات الحربية.
# الإدخال
في سطر الإدخال الأول، يتم تقديم العدد $n$، الذي يُمثل عدد الطائرات الحربية. ثم في السطر التالي، يتم تقديم ارتفاع الطائرات الحربية الـ $n$ بترتيب كسلسلة من الأعداد $h_i$.
$$ 1 \leq n \leq 100\ 000 $$
$$ 1 \leq h_i \leq 100\ 000 $$
# الإخراج
في الإخراج، قم بطباعة مجموع الأعداد الأستراتيجة للطائرات.
# مثال
## نموذج إدخال 1
```
5
5 4 3 7 6
```
## نموذج إخراج 1
```
4
```
<details>
<summary>توضيح النموذج 1</summary>
الطائرة الحربية الأولى، التي يبلغ ارتفاعها 5، تقع في الخلف ولديها القدرة على استهداف الطائرتين الحربيتين الثانية والثالثة. وبالتالي، العدد الاستراتيجي لها هو 2. الطائرة الحربية الثانية يمكنها استهداف الطائرة الحربية الثالثة، والعدد الاستراتيجي لها هو 1. أما الطائرة الحربية الثالثة، فلا تستطيع استهداف الطائرتين الحربيتين الرابعة والخامسة بسبب ارتفاعها الأقل، لذا العدد الاستراتيجي لها هو 0. وبنفس الطريقة، العدد الاستراتيجي للطائرة الحربية الرابعة هو 1 والعدد الاستراتيجي للطائرة الحربية الخامسة هو 0.
بالتالي، مجموع أعداد الاستراتيجيات لجميع الطائرات الحربية سيكون 4.
</details>
## نموذج إدخال 2
```
30
16 6 17 15 21 18 20 28 3 4 11 9 5 13 27 29 10 7 12 25 2 19 30 24 23 26 1 8 22 14
```
## نموذج إخراج 2
```
202
```
<details class="green">
<summary>
طريقة الحل
</summary>
```python
def merge(left, right):
merged = []
inversions = 0
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
inversions += len(left) - i
merged.extend(left[i:])
merged.extend(right[j:])
return merged, inversions
def merge_sort(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, inv_left = merge_sort(arr[:mid])
right, inv_right = merge_sort(arr[mid:])
merged, inversions = merge(left, right)
return merged, inversions + inv_left + inv_right
n = int(input())
heights = list(map(int, input().split()))
sorted_heights, inversions = merge_sort(heights)
print(inversions)
```
النص التوضيحي للكود لحساب عدد الانعكاسات في القائمة باستخدام تقنية التقسيم والحل (Divide and Conquer) وبتعقيد زمني O(n log n):
هذا الكود يهدف إلى حساب عدد الانعكاسات في قائمة معينة من الأعداد. الانعكاس هو عبارة عن زوج من العناصر في القائمة حيث العنصر الأيمن أصغر من العنصر الأيسر. على سبيل المثال، في القائمة [5، 4، 3، 7، 6]، هناك أربع انعكاسات: (5، 4)، (5، 3)، (7، 6)، و (7، 6).
**الخوارزمية:**
الخوارزمية المستخدمة لحساب عدد الانعكاسات هي خوارزميةالتقسيم و الحل او فرق تسد. إليك كيف تعمل الخوارزمية:
1. **التقسيم:** تقسم القائمة إلى نصفين تقريبًا. يتم ذلك عن طريق تقسيم القائمة إلى جزئين متساويين (أو تقريباً متساويين) في كل تراكم.
2. **الحل:** يتم حساب عدد الانعكاسات في الجزء الأيمن والجزء الأيسر من القائمة بشكل منفصل باستخدام الخوارزمية نفسها. ثم يتم دمج الجزئين وحساب عدد الانعكاسات الإضافية التي تحدث عند الدمج.
3. **الدمج:** يتم دمج الجزئين الأيمن والأيسر لإنشاء قائمة مرتبة. خلال عملية الدمج، يتم حساب عدد الانعكاسات الإضافية التي تحدث عند دمج القائمتين.
4. **الجمع:** يتم حساب إجمالي عدد الانعكاسات باجمع الانعكاسات من الجزئين الأيمن والأيسر والانعكاسات الإضافية التي تحدث أثناء الدمج.
**المخرجات:**
بعد تنفيذ الكود، سيتم طباعة إجمالي عدد الانعكاسات في القائمة المعطاة.
**مثال:**
في سياق مثال القائمة [5، 4، 3، 7، 6] السابق، ستكون الإجابة 4. يتم ذلك بواسطة تقسيم القائمة إلى نصفين: [5، 4، 3] و [7، 6]. بعد ذلك، يتم حساب الانعكاسات في النصفين الأيمن والأيسر بشكل منفصل، ومن ثم يتم دمج النصفين وحساب الانعكاسات الإضافية عند الدمج.
</details>