Masala #9ZRXFQ8H6F

Xotira 16 MB Vaqt 1000 ms
14

N + 1 ta son

Sizga N + 1 ta 1 dan N gacha bo'lgan sonlardan tashkil topgan massiv berilgan, aynan N tasi 1 martadan qatnashgan qaysidir element 2 marta uchraydi

Har bir uzunlikda necha xil qism ketma-ketlik borligini aniqlaydigan dastur tuzib bering!

Qism ketma-ketlikdagi elementlar qo'shni bo'lishi shart emas, masalan: {1, 2, 5} va {1, 3, 6} lar {1,2,3,4,5,6} massivning qism ketma-ketligi hisoblanadi ammo {1, 5, 2} yoki {6, 1} lar emas

Eslatma: 2 ta qism ketma-ketlik turli xil hisoblanmaydi agar ulardagi elementlar bir xil bo'lsa,  hattoki biz bergan massivdagi o'rinlari turli xil bo'lsa ham!


Kiruvchi ma'lumotlar:

Birinchi qatorda N (0 < N ≤ 105) butun soni beriladi 

Keyingi qatorda N + 1 ta butun sonlar Ai (0 < Ai ≤ N) massiv elementlari beriladi


Chiquvchi ma'lumotlar:

N + 1 ta qatorda bir uzunlik uchun necha xil ketma-ketlik borligini 109+7 ga bo'lgandagi qoldig'ini chiqaring


Misollar
# input.txt output.txt
1
2
1 2 2
2
2
1
2
2
2 1 2
2
3
1
Izoh:

Namunadagi testda

2 ta 1 uzunlikdagi qism ketma-ketlik mavjud bular: {1} va {2}

2 ta 1 uzunlikdagi qism ketma-ketlik mavjud bular: {1, 2} va {2, 2}

1 ta 3 uzunlikdagi qism ketma-ketlik mavjud bular: {1, 2, 2}