Дана довольно банальная задача. Дан массив состоящий из N чисел (N<=10^5). Нужно для каждого числа вывести кол-во чисел, которые лежат справа и которые меньше его самого. Помогите пожалуйста как решать подобную задачу.

Дан двудольный неориентированный граф состоящий из N вершин в каждой доле. N<=1000. Нужно взять из левой доли как можно меньше вершин, так чтобы степени у всех вершин в правой доли были больше или равны единице. Если мы берем вершину, то мы берем и все ребра принадлежащие этой вершине. Помогите пожалуйста как решать!